Đường dẫn ngắn nhất cho tất cả các cặp

Thuật toán đường đi ngắn nhất của tất cả các cặp còn được gọi là thuật toán Floyd-Warshall được sử dụng để tìm tất cả các bài toán về đường đi ngắn nhất của cặp từ một đồ thị có trọng số cho trước. Kết quả của thuật toán này, nó sẽ tạo ra một ma trận, sẽ đại diện cho khoảng cách tối thiểu từ bất kỳ nút nào đến tất cả các nút khác trong biểu đồ.

Lúc đầu, ma trận đầu ra giống như ma trận chi phí đã cho của đồ thị. Sau đó, ma trận đầu ra sẽ được cập nhật với tất cả các đỉnh k là đỉnh trung gian.

Độ phức tạp về thời gian của thuật toán này là O (V3), ở đây V là số đỉnh trong đồ thị.

Đầu vào - Ma trận chi phí của biểu đồ.

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

Đầu ra - Ma trận của tất cả các cặp đường đi ngắn nhất.

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

Thuật toán

floydWarshal (chi phí)

Đầu vào - Ma trận chi phí của Đồ thị đã cho.

Đầu ra - Ma trận để tìm đường đi ngắn nhất giữa bất kỳ đỉnh nào đến đỉnh bất kỳ.

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

Ví dụ

#include<iostream>
#include<iomanip>
#define NODE 7
#define INF 999
using namespace std;
//Cost matrix of the graph
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 << "The matrix:" << 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();
}

Đầu ra

The matrix:
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