设计与分析 - Floyd Warshall 算法

Floyd-Warshall 算法是一种图算法，用于查找加权图中存在的所有顶点之间的最短路径。该算法与其他最短路径算法不同；简单来说，该算法使用图中的每个顶点作为枢轴来检查它是否提供从一个点到另一个点的最短路径。

Floyd-Warshall 算法适用于有向和无向加权图，除非这些图不包含任何负循环。负循环意味着图中所有边的总和不得为负数。

由于该算法处理重叠的子问题 - 存储作为枢轴的顶点找到的路径以用于解决后续步骤 - 它使用动态规划方法。

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

弗洛伊德-沃歇尔算法

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

算法

步骤 1 -使用图中存在的所有边的成本构造一个邻接矩阵A。如果两个顶点之间没有路径，则将该值标记为 ∞。

步骤 2 -从A导出另一个邻接矩阵A 1 ，保持A 1中原始邻接矩阵的第一行和第一列不变。对于其余值，假设A 1 [i,j]，如果A[i,j]>A[i,k]+A[k,j]则将A 1 [i,j]替换为A[i, k]+A[k,j]。否则，请勿更改这些值。在此步骤中，k = 1（第一个顶点充当枢轴）。

步骤 3 -通过更改每个枢轴顶点的k值，对图中的所有顶点重复步骤 2，直到获得最终矩阵。

步骤 4 - 最终获得的邻接矩阵是具有所有最短路径的最终解决方案。

伪代码

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

例子

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

有向加权图

解决方案

步骤1

以所有距离为值构造一个邻接矩阵A。

$$A=\begin{矩阵} 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{矩阵}$$

第2步

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

$$A=\begin{矩阵} 0 & 5& \infty & 6& \infty \\ \infty & & & & \\ 3& & & & \\ \infty& & & & \\ 2& & & & \\ \end{矩阵}$$

$$A_{1}=\begin{矩阵} 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{矩阵}$$

步骤3

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

$$A_{2}=\begin{矩阵} & 5& & & \\ \infty & 0& 1& \infty& 7\\ & 8& & & \\ & \infty& & & \\ & 7& & & \\ \end{矩阵}$$

$$A_{2}=\begin{矩阵} 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{矩阵}$$

步骤4

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

$$A_{3}=\begin{矩阵} & & 6& & \\ & & 1& & \\ 3 & 8& 0& 4& 15\\ & & 2& & \\ & & 8& & \\ \end{矩阵}$ $

$$A_{3}=\begin{矩阵} 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{矩阵}$$

步骤5

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

$$A_{4}=\begin{矩阵} & & & 6& \\ & & & 5& \\ & & & 4& \\ 5 & 10& 2& 0& 3\\ & & & 5& \\ \end{矩阵}$ $

$$A_{4}=\begin{矩阵} 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{矩阵}$$

步骤6

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

$$A_{5}=\begin{矩阵} & & & & 9 \\ & & & & 7\\ & & & & 7\\ & & & & 3\\ 2 & 7& 7& 5& 0 \\ \end {矩阵}$$

$$A_{5}=\begin{矩阵} 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{矩阵}$$

分析

从上面的伪代码可以看出，Floyd-Warshall 算法使用三个 for 循环来查找图中所有顶点对之间的最短距离。因此，Floyd-Warshall 算法的时间复杂度为O(n 3 )，其中“n”是图中的顶点数。该算法的空间复杂度为O ( n 2 )。

例子

以下是 Floyd Warshall 算法的实现，使用成本邻接矩阵查找图中的最短路径 -

C C++ Java Python 
#include <stdio.h>
void floyds(int b[3][3]) {
   int i, j, k;
   for (k = 0; k < 3; k++) {
      for (i = 0; i < 3; i++) {
         for (j = 0; j < 3; j++) {
            if ((b[i][k] * b[k][j] != 0) && (i != j)) {
               if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                  b[i][j] = b[i][k] + b[k][j];
               }
            }
         }
      }
   }
   for (i = 0; i < 3; i++) {
      printf("\nMinimum Cost With Respect to Node: %d\n", i);
      for (j = 0; j < 3; j++) {
         printf("%d\t", b[i][j]);
      }
   }
}

int main() {
   int b[3][3] = {0};
   b[0][1] = 10;
   b[1][2] = 15;
   b[2][0] = 12;
   floyds(b);
   return 0;
}

输出

Minimum Cost With Respect to Node: 0
0	10	25	
Minimum Cost With Respect to Node: 1
27	0	15	
Minimum Cost With Respect to Node: 2
12	22	0	

#include <iostream>
using namespace std;
void floyds(int b[][3]){
   int i, j, k;
   for (k = 0; k < 3; k++) {
      for (i = 0; i < 3; i++) {
         for (j = 0; j < 3; j++) {
            if ((b[i][k] * b[k][j] != 0) && (i != j)) {
               if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                  b[i][j] = b[i][k] + b[k][j];
               }
            }
         }
      }
   }
   for (i = 0; i < 3; i++) {
      cout<<"\nMinimum Cost With Respect to Node:"<<i<<endl;
      for (j = 0; j < 3; j++) {
         cout<<b[i][j]<<"\t";
      }
   }
}
int main(){
   int b[3][3];
   for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
         b[i][j] = 0;
      }
   }
   b[0][1] = 10;
   b[1][2] = 15;
   b[2][0] = 12;
   floyds(b);
   return 0;
}

输出

Minimum Cost With Respect to Node:0
0  10  25	
Minimum Cost With Respect to Node:1
27  0  15	
Minimum Cost With Respect to Node:2
12  22  0

import java.util.Arrays;
public class Main {
   public static void floyds(int[][] b) {
      int i, j, k;
      for (k = 0; k < 3; k++) {
         for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
               if ((b[i][k] * b[k][j] != 0) && (i != j)) {
                  if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
                     b[i][j] = b[i][k] + b[k][j];
                  }
               }
            }
         }
      }
      for (i = 0; i < 3; i++) {
         System.out.println("\nMinimum Cost With Respect to Node:" + i);
         for (j = 0; j < 3; j++) {
            System.out.print(b[i][j] + "\t");
         }
      }
   }
   public static void main(String[] args) {
      int[][] b = new int[3][3];
      for (int i = 0; i < 3; i++) {
         Arrays.fill(b[i], 0);
      }
      b[0][1] = 10;
      b[1][2] = 15;
      b[2][0] = 12;
      floyds(b);
   }
}

输出

Minimum Cost With Respect to Node:0
0  10  25	
Minimum Cost With Respect to Node:1
27  0  15	
Minimum Cost With Respect to Node:2
12  22  0		

import numpy as np
def floyds(b):
    for k in range(3):
        for i in range(3):
            for j in range(3):
                if (b[i][k] * b[k][j] != 0) and (i != j):
                    if (b[i][k] + b[k][j] < b[i][j]) or (b[i][j] == 0):
                        b[i][j] = b[i][k] + b[k][j]
    for i in range(3):
        print("\nMinimum Cost With Respect to Node:", i)
        for j in range(3):
            print(b[i][j], end="\t")
b = np.zeros((3, 3), dtype=int)
b[0][1] = 10
b[1][2] = 15
b[2][0] = 12
#calling the method
floyds(b)

输出

Minimum Cost With Respect to Node: 0
0	10	25	
Minimum Cost With Respect to Node: 1
27	0	15	
Minimum Cost With Respect to Node: 2
12	22	0