# Floyd-Warshall 演算法

Floyd-Warshall 的演算法用於在具有正邊緣權重或負邊緣權重的加權圖中找到最短路徑。單次執行演算法將找到所有頂點對之間的最短路徑的長度（總和權重）。通過稍微變化，它可以列印最短路徑並可以在圖形中檢測負迴圈。Floyd-Warshall 是一種動態程式設計演算法。

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  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


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


k = 1i = 2j = 3 時距離[i] [j]-2 ，其不大於距離[i] [k] + 距離[k] [j] = -2 + 0 = -2 。所以它將保持不變。同樣，當 k = 1i = 4j = 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


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


## 列印路徑：

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²）