弗洛伊德算法

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正確處理有向圖或负权的最短路径問題，同时也被用于计算有向图的传递闭包。

Floyd-Warshall算法的时间复杂度為$O(N^3)$，空间复杂度为$O(N^2)$。

原理

Floyd-Warshall算法的原理是动态规划。

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

1. 若最短路径经过点k，则$D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$；
2. 若最短路径不经过点k，则$D_{i,j,k}=D_{i,j,k-1}$。

因此，$D_{i,j,k}=\mbox{min}(D_{i,k,k-1}+D_{k,j,k-1},D_{i,j,k-1})$。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。（见下面的算法描述）

算法描述

Floyd-Warshall算法的描述如下：

for k ← 1 to n do
  for i ← 1 to n do
    for j ← 1 to n do
      if ($D_{i,k} + D_{k,j} < D_{i,j}$) then
        $D_{i,j}$ ← $D_{i,k} + D_{k,j}$;

其中$D_{i,j}$表示由點$i$到點$j$的代價，當$D_{i,j}$為 ∞ 表示兩點之間沒有任何連接。

请参阅

• 图论最短路
• Dijkstra算法
• Bellman-Ford算法