Data Structures Algorithms 简明教程
Floyd Warshall Algorithm
Floyd-Warshall 算法是一种图算法，用于找到加权图中所有顶点之间的最短路径。此算法与其他最短路径算法不同；简单来说，此算法将图中的每个顶点用作枢纽，以检查它是否提供从一点到另一点的最短路径。
Floyd-Warshall 算法适用于有向和无向加权图，除非这些图不包含任何负环。负环是指图中所有边的总和不得导致负数。
由于算法处理重叠的子问题（由充当枢纽的顶点找到的路径存储下来以解决下一步），它使用动态规划方法。
Floyd-Warshall 算法是全对最短路径算法中的一种方法，它使用图的邻接矩阵表示法求解。
Floyd-Warshall Algorithm
考虑一个图， G = {V, E} ，其中 V 是图中存在的所有顶点组成的集合，E 是图中所有边组成的集合。图， G ，以邻接矩阵的形式表示， A ，包含连接两个顶点的每条边的所有权重。
Algorithm
Step 1 − 构造邻接矩阵 A ，其中包含图中存在的边所有成本。如果两个顶点之间没有路径，则将值标记为 ∞。
Step 2 − 从 A 中派生一个 A1 ，同时保持原始邻接矩阵中第一行和第一列在 A1 中的完整性。对于其余值，例如 A1[i,j] ，如果 A[i,j]>A[i,k]+A[k,j] ，则用 A[i,k]+A[k,j] 替换 A1[i,j] 。否则，不更改值。在此步骤中， k = 1 （作为透视点的第一个顶点）。
Step 3 − 通过更改每个透视点顶点的 k 值，对图中所有顶点重复 Step 2 ，直到得到最终矩阵。
Step 4 − 得到的最终邻接矩阵是包含所有最短路径的最终解。
Pseudocode
Floyd-Warshall(w, n){ // w: weights, n: number of vertices
for i = 1 to n do // initialize, D (0) = [wij]
for j = 1 to n do{
d[i, j] = w[i, j];
}
for k = 1 to n do // Compute D (k) from D (k-1)
for i = 1 to n do
for j = 1 to n do
if (d[i, k] + d[k, j] < d[i, j]){
d[i, j] = d[i, k] + d[k, j];
}
return d[1..n, 1..n];
}
Solution
Step 1
用所有距离作为值构造一个邻接矩阵 A 。
A=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & 0& 1& \infty& 7\\ 3 & \infty& 0& 4& \infty\\ \infty & \infty& 2& 0& 3\\ 2& \infty& \infty& 5& 0\\ \end{matrix}
Step 2
将上述邻接矩阵视为输入，通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0。将 k = 1 ，并将所有其他值替换为 A[i,k]+A[k,j] 。
A=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & & & & \\ 3& & & & \\ \infty& & & & \\ 2& & & & \\ \end{matrix}
A_{1}=\begin{matrix} 0 & 5& \infty & 6& \infty \\ \infty & 0& 1& \infty& 7\\ 3 & 8& 0& 4& \infty\\ \infty & \infty& 2& 0& 3\\ 2& 7& \infty& 5& 0\\ \end{matrix}
Step 3
将上述邻接矩阵视为输入，通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0。将 k = 1 ，并将所有其他值替换为 A[i,k]+A[k,j] 。
A_{2}=\begin{matrix} & 5& & & \\ \infty & 0& 1& \infty& 7\\ & 8& & & \\ & \infty& & & \\ & 7& & & \\ \end{matrix}
A_{2}=\begin{matrix} 0 & 5& 6& 6& 12 \\ \infty & 0& 1& \infty& 7\\ 3 & 8& 0& 4& 15\\ \infty & \infty& 2& 0& 3\\ 2 & 7& 8& 5& 0 \\ \end{matrix}
Step 4
将上述邻接矩阵视为输入，通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ，并将所有其他值替换为 A[i,k]+A[k,j] 。
A_{3}=\begin{matrix} & & 6& & \\ & & 1& & \\ 3 & 8& 0& 4& 15\\ & & 2& & \\ & & 8& & \\ \end{matrix}
A_{3}=\begin{matrix} 0 & 5& 6& 6& 12 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 15\\ 5 & 10& 2& 0& 3\\ 2 & 7& 8& 5& 0 \\ \end{matrix}
Step 5
将上述邻接矩阵视为输入，通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ，并将所有其他值替换为 A[i,k]+A[k,j] 。
A_{4}=\begin{matrix} & & & 6& \\ & & & 5& \\ & & & 4& \\ 5 & 10& 2& 0& 3\\ & & & 5& \\ \end{matrix}
A_{4}=\begin{matrix} 0 & 5& 6& 6& 9 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 7\\ 5 & 10& 2& 0& 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}
Step 6
将上述邻接矩阵视为输入，通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ，并将所有其他值替换为 A[i,k]+A[k,j] 。
A_{5}=\begin{matrix} & & & & 9 \\ & & & & 7\\ & & & & 7\\ & & & & 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}
A_{5}=\begin{matrix} 0 & 5& 6& 6& 9 \\ 4 & 0& 1& 5& 7\\ 3 & 8& 0& 4& 7\\ 5 & 10& 2& 0& 3\\ 2 & 7& 7& 5& 0 \\ \end{matrix}