全对最短路径算法
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²） 。