算法——弗洛伊德算法（Floyd-Warshall）（图论）（c++）-Toy模板网

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

（蒟蒻的第四篇文章，希望dalao勿喷）

（希望没问题）

声明：

1.本人变量定义的名称很low

2.本人用的方法也很low

3.但我觉得文章应该不low ~~（盲目自信）~~

第四篇文章讲讲Floyd算法

Floyd算法是一种寻找最短路径的常见算法，其特点是：短，好理解（虽然其他算法也挺好理解的

思路

Floyd算法的主要思路是在于：

比如你要坐飞机从A城到B城，结果你发现A到B的直达航班要999元！于是你漫无目的地继续看其他航班信息，结果突然发现在A和B中间，还有一个C城！而且A到C和B到C的价格都很便宜，加在一起只需要998元！于是你高兴地购买了一张A到C和一张C到B的机票，省了一块钱诶！

例子有点离谱，但算法的思路大概就是这个样子：在目标的两个点中找到第三个所谓的C点，如果如上面例子一样，要节省一些“钱”的话就更新两个目标点的权值（甚至可以更新原本是∞的权值！

主体代码

其实听起来很牛*的样子（实际上也很牛*，但，其实主体代码真的很很很很很很很很很很很很短，emmm，可以直接压缩到4行~~（实际上肯定有人能“压缩到更短”~~

行了，啥也别说了，上代码！（只写了主体代码

//Floyd-Warshall算法 
	for(int c=1;c<=n;c++) //枚举C点 
		for(int i=1;i<=n;i++) //i j 分别就是例子中的A B城 
			for(int j=1;j<=n;j++)
				book[i][j]=max(book[i][j],book[i][c]+book[c][j]);//判断经过C是否要省一些“钱” 
	//真的只有4行！！！

但相信大家一看到这个三层循环，就知道事情不简单，时间复杂度O（n^3）！起飞了昂（~~简单代码漏洞还是大啊！~~

这里的主体代码的第4行也可以换成~~（虽然可能没什么用~~

if(book[i][j]>book[i][c]+book[c][j])
    book[i][j]=book[i][c]+book[c][j];

来练一题

P3371 【模板】单源最短路径（弱化版）

(题目传送门)

转载自洛谷

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u \to vu→v 的，长度为 ww 的边。

输出格式

输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 2^{31}-1231−1。

输入输出样例

输入 #1

输出 #1

0 2 4 3

说明/提示

【数据范围】
对于 20\%20% 的数据：1\le n \le 51≤n≤5，1\le m \le 151≤m≤15；
对于 40\%40% 的数据：1\le n \le 1001≤n≤100，1\le m \le 10^41≤m≤104；
对于 70\%70% 的数据：1\le n \le 10001≤n≤1000，1\le m \le 10^51≤m≤105；
对于 100\%100% 的数据：1 \le n \le 10^41≤n≤104，1\le m \le 5\times 10^51≤m≤5×105，1\le u,v\le n1≤u,v≤n，w\ge 0w≥0，\sum w< 2^{31}∑w<231，保证数据随机。

对于真正 100\%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

算法——弗洛伊德算法（Floyd-Warshall）（图论）（c++）