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