弗洛伊德算法

August 8, 2018 · View on GitHub

在计算机科学中弗洛伊德算法是一种用于可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题. 单次执行算法将找到所有顶点对之间的最短路径的长度 (总和权重) . 虽然它不返回路径本身的细节,但可以通过对算法的简单修改来重建路径.

算法

一个有向图G=（V，E）

用邻接矩阵map[][]存储有向图，用dist[i][j]表示i到j的最短路径。设G的顶点为V={1,2,3...n}，对于任意一对顶点i,j属于V，假设i到j有路径且中间节点皆属于集合{1,2,3...k}，P是其中的一条最小权值路径。就是i到j的最短路径P所通过的中间顶点最大不超过k。

设 D_i,j,k 为从 i 到 j 的, 只以(1..k)集合中的节点为中间节点的最短路径的长度。

若最短路径经过点k，则 $if$
若最短路径不经过点k，则 $ele$

因此, $end$

这个公式是弗洛伊德算法的核心.

例

上面的算法在左下方的图表上执行:

Example

在下表中i是行号和j是列号.

k = 0

	1	2	3	4
1	0	∞	-2	∞
2	4	0	3	∞
3	∞	∞	0	2
4	∞	-1	∞	0

k = 1

	1	2	3	4
1	0	∞	-2	∞
2	4	0	2	∞
3	∞	∞	0	2
4	∞	-	∞	0

k = 2

	1	2	3	4
1	0	∞	-2	∞
2	4	0	2	∞
3	∞	∞	0	2
4	3	-1	1	0

k = 3

	1	2	3	4
1	0	∞	-2	0
2	4	0	2	4
3	∞	∞	0	2
4	3	-1	1	0

k = 4

	1	2	3	4
1	0	-1	-2	0
2	4	0	2	4
3	5	1	0	2
4	3	-1	1	0

算法

例

参考