Floyd-Warshall 全源最短路径计算器

什么是Floyd-Warshall 全对最短路计算器？

Floyd-Warshall 是全源最短路径算法：一次运行得到任意两点间的最短距离。

核心思想是动态规划：设 d_k(i,j) 为只允许前 k 个顶点作中转时 i 到 j 的最短距离。

转移方程 d_k(i,j) = min(d_{k−1}(i,j), d_{k−1}(i,k) + d_{k−1}(k,j))。

三个嵌套循环按 k、i、j 顺序松弛，可用滚动数组原地更新。

复杂度 O(V³)，顶点较少时比跑 V 次 Dijkstra 更简洁。

如何使用Floyd-Warshall 全对最短路计算器

1. 1

   选择一个预设图。

2. 2

   结果区显示顶点数、松弛更新次数，以及从每个顶点出发的距离行。

3. 3

   每行是从该顶点到其余各顶点的最短距离，∞ 表示不可达。

4. 4

   对角线为 0，可用对称性核对无向图输入是否正确。

计算示例

注意事项

• 要求图中无负权回路；存在负回路时最短路无定义。

• 初始化：对角线为 0，直接相连的边填权重，其余为 ∞。

• 松弛更新次数反映图的中转价值：次数越多，绕行收益越大。

• 无向图距离矩阵应关于对角线对称，可作为自检。

常见问题

参考资料

1. [1]NIST DLMF：数学函数与公式权威参考
2. [2]Wolfram MathWorld：数学条目百科