Floyd算法

如果想找到每对顶点之间的最短路径（All-Pairs Shortest Path），可以使用 Floyd 算法。

基本思想（动态规划）

Floyd 算法是一个动态规划算法。

• 如果 $v_i$ 与 $v_j$ 之间有有向边，则 $v_i$ 与 $v_j$ 之间有一条路径，但不一定是最短的，也许经过某些中间点会使路径长度更短。
• 经过哪些中间点会使路径长度缩短呢？经过哪些中间点会使路径长度最短呢？
• 只需尝试在原路径中间加入其它顶点作为中间顶点，然后不断地调整当前路径（和路径长度）。

数据结构

• 图的存储结构：带权的有向图采用邻接矩阵 C[n][n] 存储。
• 数组 D[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式： $$D^k[i][j]=\min \{D^{k-1}[i][j],D^{k-1}[i][k]+D^{k-1}[k][j]\}$$ 其中 $0\le k\le n-1$。
• 数组 P[n][n]：存放从 $v_i$ 到 $v_j$ 求得的最短路径。初始时，$P[i][j]=-1$。

算法步骤

1. 初始化 $D^0=C$（邻接矩阵），$P$ 为路径矩阵。
2. 依次将每个顶点 k 作为中间顶点，更新 D 和 P：
   • 若 $D[i][k]+D[k][j]<D[i][j]$，则更新 $D[i][j]$ 为该较小值，并将 $P[i][j]$ 更新为 $k$。
3. 经过 $n$ 次迭代后，$D$ 中即为所有顶点对之间的最短路径长度。

限制条件

• Floyd 算法要求图中不能有负权值的回路（负权回路），但允许有负权值的边。

链接到

• 上一个知识点：7.11 Dijkstra算法
• 下一个知识点：无（本章最后一个知识点）