Floyd Warshall算法

Floyd-Warshall算法用于从给定的加权图中查找所有对最短路径问题。作为该算法的结果，它将生成一个矩阵，该矩阵将表示从图中任何节点到所有其他节点的最小距离。

首先，输出矩阵与图的给定成本矩阵相同。此后，将使用所有顶点k作为中间顶点更新输出矩阵。

该算法的时间复杂度为O（V ^ 3），其中V是图中顶点的数量。

输入输出

Input: The 图的成本矩阵.
0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0

Output:
Matrix of all pair shortest path.
0 3 4 5 6 7 7
3 0 2 1 3 4 4
4 2 0 1 3 2 3
5 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0

算法

floydWarshal(cost)

输入-给定图的成本矩阵。

输出：矩阵到任意顶点到任意顶点之间的最短路径。

Begin
   for k := 0 to n, do
      for i := 0 to n, do
         for j := 0 to n, do
            if cost[i,k] + cost[k,j] < cost[i,j], then
               cost[i,j] := cost[i,k] + cost[k,j]
         done
      done
   done
   display the current cost matrix
End

示例

#include<iostream>
#include<iomanip>
#define NODE 7
#define INF 999
using namespace std;

//图的成本矩阵
int costMat[NODE][NODE] = {
   {0, 3, 6, INF, INF, INF, INF},
   {3, 0, 2, 1, INF, INF, INF},
   {6, 2, 0, 1, 4, 2, INF},
   {INF, 1, 1, 0, 2, INF, 4},
   {INF, INF, 4, 2, 0, 2, 1},
   {INF, INF, 2, INF, 2, 0, 1},
   {INF, INF, INF, 4, 1, 1, 0}
};

void floydWarshal() {
   int cost[NODE][NODE];    //defind to store shortest distance from any node to any node
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         cost[i][j] = costMat[i][j];     //copy costMatrix to new matrix

   for(int k = 0; k<NODE; k++) {
      for(int i = 0; i<NODE; i++)
         for(int j = 0; j<NODE; j++)
            if(cost[i][k]+cost[k][j] < cost[i][j])
               cost[i][j] = cost[i][k]+cost[k][j];
   }

   cout << "矩阵：" << endl;
   for(int i = 0; i<NODE; i++) {
      for(int j = 0; j<NODE; j++)
         cout << setw(3) << cost[i][j];
      cout << endl;
   }
}

int main() {
   floydWarshal();
}

输出结果

矩阵：
0  3  5  4  6  7  7
3  0  2  1  3  4  4
5  2  0  1  3  2  3
4  1  1  0  2  3  3
6  3  3  2  0  2  1
7  4  2  3  2  0  1
7  4  3  3  1  1  0