Floyd-Warshall 演算法
Floyd-Warshall 的演算法用於在具有正邊緣權重或負邊緣權重的加權圖中找到最短路徑。單次執行演算法將找到所有頂點對之間的最短路徑的長度（總和權重）。通過稍微變化，它可以列印最短路徑並可以在圖形中檢測負迴圈。Floyd-Warshall 是一種動態程式設計演算法。
我們來看一個例子。我們將在此圖上應用 Floyd-Warshall 的演算法： 
我們要做的第一件事是，我們採用兩個 2D 矩陣。這些是鄰接矩陣 。矩陣的大小將是頂點的總數。對於我們的圖表，我們將採用 4 * 4 矩陣。在距離矩陣是要儲存至今兩個頂點之間發現的最小距離。首先，對於邊緣，如果在 uv 和距離/重量之間存在邊緣是 w ，我們將儲存：distance[u][v] = w。對於不存在的所有邊緣，我們將放置無窮大。該路徑矩陣是兩個頂點之間再生最短距離路徑。所以一開始，如果有之間的路徑 U 和 v ，我們打算把 path[u][v] = u。這意味著從頂點 -u 到頂點 -v 的最佳方法是使用連線 v 與 u 的邊。如果兩個頂點之間沒有路徑，我們將把 N 放在那裡，表明現在沒有可用的路徑。我們圖表的兩個表格如下： **** **** **** ****
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 6 | 15 | | 1 | N | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | inf | 0 | -2 | inf | | 2 | N | N | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | inf | inf | 0 | 2 | | 3 | N | N | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | inf | inf | 0 | | 4 | 4 | N | N | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
由於沒有環路，則對角線設定 N 。與頂點本身的距離為 0 。
為了應用 Floyd-Warshall 演算法，我們將選擇一箇中間頂點 k 。然後對於每個頂點 i ，我們將檢查我們是否可以從 i 到 k 再到 k 到 j ，其中 j 是另一個頂點並且最小化從 i 到 j 的成本。如果當前距離[i] [j] 大於距離[i] [k] + 距離[k] [j] ，我們將把距離[i] [j] 等於這兩個距離的總和。並且路徑[i] [j] 將被設定為路徑[k] [j] ，因為從 i 到 k ，然後從 k 到 j 更好。所有頂點將被選為 k 。我們將有 3 個巢狀迴圈：對於 k 從 1 到 4，我從 1 到 4， j 從 1 到 4。我們要檢查：
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
那麼我們基本上檢查的是，*對於每對頂點，我們通過另一個頂點獲得更短的距離嗎？*我們圖表的總運算元為 4 * 4 * 4 = 64 。這意味著我們將進行 64 次檢查。我們來看幾個：
當 k = 1 ， i = 2 且 j = 3 時，距離[i] [j] 為 -2 ，其不大於距離[i] [k] + 距離[k] [j] = -2 + 0 = -2 。所以它將保持不變。同樣，當 k = 1 ， i = 4 且 j = 2 時，距離[i] [j] = 無窮大，大於距離[i] [k] + 距離[k] [j] = 1 + 3 = 4 。所以我們把距離[i] [j] = 4 ，並且我們把路徑[i] [j] = 路徑[k] [j] = 1 。這意味著，從頂點 -4 到頂點 -2 ，路徑 4-> 1-> 2 比現有路徑短。這就是我們填充兩個矩陣的方式。此處顯示每個步驟的計算。在進行必要的更改後，我們的矩陣將如下所示：
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 1 | 3 | | 1 | N | 1 | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | 1 | 0 | -2 | 0 | | 2 | 4 | N | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | 3 | 6 | 0 | 2 | | 3 | 4 | 1 | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | 4 | 2 | 0 | | 4 | 4 | 1 | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
這是我們最短的距離矩陣。例如，從 1 到 4 的最短距離是 **3，**並且 4 到 3 之間的最短距離是 2 。我們的虛擬碼將是：
Procedure Floyd-Warshall(Graph):
for k from 1 to V // V denotes the number of vertex
for i from 1 to V
for j from 1 to V
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
end for
end for
end for
列印路徑：
要列印路徑，我們將檢查路徑矩陣。要列印從 u 到 v 的路徑，我們將從路徑[u] [v]開始。我們將設定保持更改 v = path [u] [v]，直到我們找到路徑[u] [v] = u 並在路徑中推送路徑[u] [v]的每個值。找到你之後，我們將列印你並開始從堆疊中彈出專案並列印它們。這是有效的，因為路徑矩陣儲存頂點的值，該頂點與任何其他節點共享到 v 的最短路徑。虛擬碼將是：
Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
S.push(Path[source][destination])
destination := Path[source][destination]
end while
print -> source
while S is not empty
print -> S.pop
end while
查詢負邊迴圈：
為了確定是否存在負邊緣週期，我們需要檢查距離矩陣的主對角線。如果對角線上的任何值為負，則表示圖中存在負迴圈。
複雜：
Floyd-Warshall 演算法的複雜性為 O（V³） ，空間複雜度為： O（V²） 。