Thuật toán Floyd-Warshall (Đường đi ngắn nhất mọi cặp)

Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số (có thể âm, nhưng không chu trình âm). Kết quả là ma trận khoảng cách ngắn nhất.

Ý tưởng: Cập nhật ma trận khoảng cách bằng cách cho phép các đỉnh trung gian k từ 0 đến n-1.

Đầu vào và Đầu ra

Đầu vào: Ma trận chi phí 7x7 (INF = 999)
Đầu ra: Ma trận khoảng cách ngắn nhất mọi cặp

Thuật toán

1. Sao chép ma trận chi phí vào cost.
2. Với k từ 0 đến n-1:
   • Với mọi cặp (i, j): nếu cost[i][k] + cost[k][j] < cost[i][j] thì cập nhật.
3. In ma trận cost.

Độ phức tạp: O(V³) thời gian, O(V²) không gian.

Ví dụ C++

#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];
    for(int i=0;i<NODE;i++) for(int j=0;j<NODE;j++) cost[i][j] = costMat[i][j];

    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:\n";
    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(); }

Kết quả

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