【图论】Floyd算法

这篇具有很好参考价值的文章主要介绍了【图论】Floyd算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.简介

【图论】Floyd算法,图论,图论,算法

 Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。

Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两个节点之间的最短路径长度,并通过不断更新这个数组来得到最终的结果。

算法的步骤如下:

  1. 初始化一个二维数组,用于存储节点之间的最短路径长度。
  2. 将数组的初始值设置为图中节点之间的直接距离,如果两个节点之间没有直接连接,则距离为无穷大。
  3. 对于每个节点k,遍历所有节点对(i, j),并尝试通过节点k来优化路径长度。如果通过节点k可以获得更短的路径,则更新数组中的值。
  4. 重复步骤3,直到所有节点对的最短路径长度都被计算出来。

Floyd算法的时间复杂度为O(n^3),其中n是图中节点的数量。它适用于解决稠密图(边数接近节点数的平方)的最短路径问题,但对于稀疏图来说,可能存在更高效的算法。

总的来说,Floyd算法是一种非常经典且实用的算法,可以在有向图或带权图中找到任意两个节点之间的最短路径。


二.存图方法

因为是解决多源最短路,所以使用邻接矩阵存图。


三.原理 

逐渐利用每个点进行搭桥,实现中转功能。过程中带有dp的思想,因为要使用搭完桥之后的最短路径进行再次搭桥,从而实现最优解。


四.核心代码

for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

五.很重要的一道题

P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


六.此题好的原因

考察了对选手floyd算法的进一步理解,而不是单纯的背板子


七.难点

最短路径是很好求的,但题目要求的时间是个大难题。有些路在一个时间点并不能用,更不能起到搭桥作用。所以输出答案时,并不能只考虑起点和终点不能走,还有考虑不能走对其他点最短路的影响。


八.解决方案

既然没到时间就不能用这个点搭桥,那我们在计算整体最短路时不用不就行了吗?在floyd算法中,第一重遍历中的k就是用这个点进行搭桥,那我们就没到时间这前就不遍历即可。文章来源地址https://www.toymoban.com/news/detail-665710.html


九.参考代码

#include<iostream>
#include<cstdio>
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];//邻接矩阵存边
inline void updata(int k){
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	if(f[i][j]>f[i][k]+f[j][k])
	f[i][j]=f[j][i]=f[i][k]+f[j][k];//用这个新的更新所有前面的 
	return;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		scanf("%d",a[i]);//依次输入每一个村庄建立完成时需要的时间
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++){
		f[i][j]=1e9;//初始化为保证它不爆炸范围内的最大值 
	}
	for(int i=0;i<n;i++)
	f[i][i]=0;
	int s1,s2,s3;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&s1,&s2,&s3);
		f[s1][s2]=f[s2][s1]=s3;//初始化边长 
	}
	int q;
	cin>>q;
	int now=0;
	for(int i=1;i<=q;i++){//处理各询问 
		scanf("%d%d%d",&s1,&s2,&s3); //s3为可用时间点 ,s1为x点,s2为y点 
		while(a[now]<=s3&&now<n){
			updata(now);//依次更新点,使它可以被用来更新其他的点 
			now++;
		}
		if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;
		else {
			if(f[s1][s2]==1e9)cout<<-1<<endl;
			else cout<<f[s1][s2]<<endl;
		}
	}
	return 0;
} 

到了这里,关于【图论】Floyd算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论:最短路(dijkstra算法、bellman算法、spfa算法、floyd算法)详细版

    终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。 话不多说下面看看最短路问题吧。 最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。 下面分为几类题目: 单源汇最短路--一个起

    2024年01月21日
    浏览(44)
  • 【图论C++】Floyd算法(多源最短路径长 及 完整路径)

    UpData Log👆 2023.9.29 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述可能不够标准,但能达其意 常见的有: DJ算法 、 Floyd算法 、 A*算法 、 Bellman-Ford 算法 、 SPFA算法 其中 A*算法 是 DJ算法 的plus版, SPFA算法 是 Bellman-Ford 算法 的plus版 算法名称 DJ算法 Floyd算法 SPFA算法

    2024年02月19日
    浏览(43)
  • 【算法基础:搜索与图论】3.4 求最短路算法(Dijkstra&bellman-ford&spfa&Floyd)

    关于最短路可见:https://oi-wiki.org/graph/shortest-path/ 无向图 是一种 特殊的 有向图。(所以上面的知识地图上没有区分边有向还是无向) 关于存储:稠密图用邻接矩阵,稀疏图用邻接表。 朴素Dijkstra 和 堆优化Dijkstra算法的 选择就在于图 是 稠密的还是稀疏的。 算法步骤: 有一

    2024年02月16日
    浏览(45)
  • 算法基础复盘笔记Day06【搜索与图论】—— Dijkstra、bellman-ford、spfa、Floyd

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月22日
    浏览(46)
  • 【图论】Floyd

    算法提高课笔记) 原题链接 农民John的农场里有很多牧区,有的路径连接一些特定的牧区。 一片所有连通的牧区称为一个牧场。 但是就目前而言,你能看到至少有两个牧区不连通。 现在,John想在农场里添加一条路径(注意,恰好一条)。 一个牧场的直径就是牧场中最远的

    2024年02月09日
    浏览(38)
  • 8.3.1 蓝桥杯图论之Floyd&Dijkstra

    在蓝桥杯等算法竞赛中,图论问题占据了重要地位,其中路径查找是一个经常出现的主题。Floyd-Warshall算法和Dijkstra算法是解决图中最短路径问题的两种经典算法。本篇博客将介绍这两种算法的原理和实现,以及它们的应用场景。 Floyd-Warshall算法是一种计算图中所有最短路径的

    2024年02月19日
    浏览(40)
  • 【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd

    今日语录: 每一次挑战都是一次成长的机会 如上所示即为做题时应对的方法 引用与稠密图,即mn^2

    2024年01月23日
    浏览(56)
  • 图论 - 最短路(Dijkstra、Bellman-Ford、SPFA、Floyd)

    单源:在边权正数时,稠密图用朴素Dijkstra,稀疏图用堆优化Dijkstra;存在负权边时,一般用SPFA,但是如果限制在k步内,则用Bellman-Ford。多源:只有Floyd,这个由于时间复杂度太高,在算法比赛中很少遇见。 1.问题描述 给定一个 n 个点 m 条边的有向图,图中可能存在重边和自

    2024年04月14日
    浏览(38)
  • Acwing.854 Floyd求最短路 (Floyd算法)

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输\\\"impossible”。 数据保证图中不存在负权回路。 第一行包含三个整数n, m, k 接下来m行,每行包含三

    2024年02月13日
    浏览(36)
  • 图算法——求最短路径(Floyd算法)

    目录 一、什么是最短路径 二、弗洛伊德(Floyd)算法 三、测试程序         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多

    2024年02月07日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包