令G的顶点为V = {1, 2 …
…
n}, 并考虑某个k的顶点的子集{1, 2 …
…
k}。对于任意一对顶点i, j∈V, 考虑从i到j的所有路径, 这些路径的中间顶点都从{1, 2 …
.. k}绘制, 并令p为其中的最小权重路径。 Floyd-Warshall算法利用路径p和从i到j的最短路径之间的链接, 其中所有中间顶点都在{1, 2 …
.. k-1}中。链接取决于k是否为路径p的中间顶点。
如果k不是路径p的中间顶点, 则路径p的所有中间顶点都在集合{1, 2?? …
…
k-1}中。因此, 从顶点i到顶点j且集合{1, 2?? …
…
.. k-1}中有所有中间顶点的最短路径也是到顶点j且集合{1中有所有中间顶点的最短路径, 2 …
…
. k}。
如果k是路径p的中间顶点, 则我们将p分解为i→k→j。
令dij(k)为从顶点i到顶点j的最短路径的权重, 其中所有中间顶点在集合{1, 2?? …
.. k}中。
递归定义为
文章图片
FLOYD - WARSHALL (W) 1. n ← rows [W]. 2. D0 ← W 3. for k ← 1 to n 4. do for i ← 1 to n 5. do for j ← 1 to n 6. do dij(k) ← min (dij(k-1), dik(k-1)+dkj(k-1) ) 7. return D(n)
Floyd-Warshall算法采用的策略是动态规划。 Floyd-Warshall算法的运行时间由3-6行循环的三重嵌套确定。第6行的每次执行花费O(1)时间。该算法因此在时间θ(n3)中运行。
示例:应用Floyd-Warshall算法构造最短路径。证明由Floyd-Warshall算法为该图计算的矩阵D(k)和π(k)。
文章图片
解:
文章图片
步骤(i)当k = 0时
文章图片
步骤(ii)当k = 1
文章图片
文章图片
文章图片
步骤(iii)当k = 2
文章图片
文章图片
步骤(iv)当k = 3
文章图片
文章图片
步骤(v)当k = 4
文章图片
文章图片
文章图片
【图论算法(Floyd-Warshall算法)】步骤(vi)当k = 5
文章图片
文章图片
TRANSITIVE- CLOSURE (G) 1. n ← |V[G]| 2. for i ← 1 to n 3. do for j ← 1 to n 4. do if i = j or (i, j) ∈ E [G] 5. the ← 1 6. else ← 0 7. for k ← 1 to n 8. do for i ← 1 to n 9. do for j ← 1 to n 10. dod ij(k) ← 11. Return T(n).
推荐阅读
- 图论算法(Johnsons算法)
- 图论算法(全对最短路径)
- 有向无环图中的单源最短路径
- 最短路径(ellman-Ford算法)
- 图论算法(Dijkstra算法)
- 图论(松弛技术)
- 图论(最短路径的表示)
- 图论(负权重边)
- 图论(单源最短路径)