带你读《图解算法小抄》二十五、图（2）https://developer.aliyun.com/article/1347771?groupCode=tech_library
4.Floyd-Warshall 算法
在计算机科学中，Floyd-Warshall 算法是一种用于在具有正或负边权重（但没有负循环）的加权图中找到最短路径的算法。该算法的一次执行可以找到所有顶点对之间的最短路径长度（加权之和）。尽管它不返回路径的详细信息，但可以通过对算法进行简单修改来重构路径。
1）算法
Floyd-Warshall 算法比较了图中每对顶点之间的所有可能路径。在图中进行 O(|V|^3) 次比较。这是非常了不起的，因为图中可能有多达 |V|^2 条边，而且需要测试每种边的组合。算法通过逐步改进两个顶点之间的最短路径估计，直到估计达到最优解。
考虑一个图 G，顶点 V 的编号从 1 到 N。进一步考虑一个函数 shortestPath(i, j, k)，它返回仅使用集合 {1, 2, ..., k} 中的顶点作为中间点的路径，从 i 到 j 的最短路径。现在，给定该函数，我们的目标是找到每个 i 到每个 j 的最短路径，只使用顶点集 {1, 2, ..., N}。
这个公式是 Floyd-Warshall 算法的核心。
2）示例
上述算法在下图中的图上执行：
下表中 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 |
∞ |
−1 |
∞ |
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 |
3）参考资料
- Wikipedia
- YouTube (by Abdul Bari)
- YouTube (by Tushar Roy)
带你读《图解算法小抄》二十五、图（4）https://developer.aliyun.com/article/1347769?groupCode=tech_library
