Data Structures Algorithms 简明教程

Floyd Warshall Algorithm

Floyd-Warshall 算法是一种图算法,用于找到加权图中所有顶点之间的最短路径。此算法与其他最短路径算法不同;简单来说,此算法将图中的每个顶点用作枢纽,以检查它是否提供从一点到另一点的最短路径。

The Floyd-Warshall algorithm is a graph algorithm that is deployed to find the shortest path between all the vertices present in a weighted graph. This algorithm is different from other shortest path algorithms; to describe it simply, this algorithm uses each vertex in the graph as a pivot to check if it provides the shortest way to travel from one point to another.

Floyd-Warshall 算法适用于有向和无向加权图,除非这些图不包含任何负环。负环是指图中所有边的总和不得导致负数。

Floyd-Warshall algorithm works on both directed and undirected weighted graphs unless these graphs do not contain any negative cycles in them. By negative cycles, it is meant that the sum of all the edges in the graph must not lead to a negative number.

由于算法处理重叠的子问题(由充当枢纽的顶点找到的路径存储下来以解决下一步),它使用动态规划方法。

Since, the algorithm deals with overlapping sub-problems – the path found by the vertices acting as pivot are stored for solving the next steps – it uses the dynamic programming approach.

Floyd-Warshall 算法是全对最短路径算法中的一种方法,它使用图的邻接矩阵表示法求解。

Floyd-Warshall algorithm is one of the methods in All-pairs shortest path algorithms and it is solved using the Adjacency Matrix representation of graphs.

Floyd-Warshall Algorithm

考虑一个图, G = {V, E} ,其中 V 是图中存在的所有顶点组成的集合,E 是图中所有边组成的集合。图, G ,以邻接矩阵的形式表示, A ,包含连接两个顶点的每条边的所有权重。

Consider a graph, G = {V, E} where V is the set of all vertices present in the graph and E is the set of all the edges in the graph. The graph, G, is represented in the form of an adjacency matrix, A, that contains all the weights of every edge connecting two vertices.

Algorithm

Step 1 − 构造邻接矩阵 A ,其中包含图中存在的边所有成本。如果两个顶点之间没有路径,则将值标记为 ∞。

Step 1 − Construct an adjacency matrix A with all the costs of edges present in the graph. If there is no path between two vertices, mark the value as ∞.

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 2 − Derive another adjacency matrix A1 from A keeping the first row and first column of the original adjacency matrix intact in A1. And for the remaining values, say A1[i,j], if A[i,j]>A[i,k]+A[k,j] then replace A1[i,j] with A[i,k]+A[k,j]. Otherwise, do not change the values. Here, in this step, k = 1 (first vertex acting as pivot).

Step 3 − 通过更改每个透视点顶点的 k 值,对图中所有顶点重复 Step 2 ,直到得到最终矩阵。

Step 3 − Repeat Step 2 for all the vertices in the graph by changing the k value for every pivot vertex until the final matrix is achieved.

Step 4 − 得到的最终邻接矩阵是包含所有最短路径的最终解。

Step 4 − The final adjacency matrix obtained is the final solution with all the shortest paths.

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];
}

Example

考虑以下有向加权图 G = {V, E} 。使用 Floyd-Warshall 算法找到图中所有顶点之间的最短路径。

Consider the following directed weighted graph G = {V, E}. Find the shortest paths between all the vertices of the graphs using the Floyd-Warshall algorithm.

directed weighted graph

Solution

Step 1

Step 1

用所有距离作为值构造一个邻接矩阵 A

Construct an adjacency matrix A with all the distances as values.

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

Step 2

将上述邻接矩阵视为输入,通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0。将 k = 1 ,并将所有其他值替换为 A[i,k]+A[k,j]

Considering the above adjacency matrix as the input, derive another matrix A0 by keeping only first rows and columns intact. Take k = 1, and replace all the other values by 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

Step 3

将上述邻接矩阵视为输入,通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0。将 k = 1 ,并将所有其他值替换为 A[i,k]+A[k,j]

Considering the above adjacency matrix as the input, derive another matrix A0 by keeping only first rows and columns intact. Take k = 1, and replace all the other values by 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

Step 4

将上述邻接矩阵视为输入,通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ,并将所有其他值替换为 A[i,k]+A[k,j]

Considering the above adjacency matrix as the input, derive another matrix A0 by keeping only first rows and columns intact. Take k = 1, and replace all the other values by 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

Step 5

将上述邻接矩阵视为输入,通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ,并将所有其他值替换为 A[i,k]+A[k,j]

Considering the above adjacency matrix as the input, derive another matrix A0 by keeping only first rows and columns intact. Take k = 1, and replace all the other values by 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

Step 6

将上述邻接矩阵视为输入,通过仅保持第一行和第一列的完整性来派生另一个矩阵 A0 。将 k = 1 ,并将所有其他值替换为 A[i,k]+A[k,j]

Considering the above adjacency matrix as the input, derive another matrix A0 by keeping only first rows and columns intact. Take k = 1, and replace all the other values by 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}

Analysis

根据上述伪代码,Floyd-Warshall 算法使用三个 for 循环来找到图中所有顶点对之间的最短距离。因此,Floyd-Warshall 算法的 time complexityO(n3) ,其中“n”是图中顶点的数量。该算法的 space complexityO(n2)

From the pseudocode above, the Floyd-Warshall algorithm operates using three for loops to find the shortest distance between all pairs of vertices within a graph. Therefore, the time complexity of the Floyd-Warshall algorithm is O(n3), where ‘n’ is the number of vertices in the graph. The space complexity of the algorithm is O(n2).

Implementation

以下是用弗洛伊德·沃舍尔算法来查找带权邻接矩阵中图中最短路径的实现 -

Following is the implementation of Floyd Warshall Algorithm to find the shortest path in a graph using cost adjacency matrix -