Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Đường đi ngắn nhất mọi cặp (All-Pairs Shortest Paths - Floyd-Warshall)


Thuật toán đườ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 từ đồ thị có trọng số. Kết quả tạo ra ma trận biểu diễn khoảng cách nhỏ nhất từ bất kỳ nút nào đến tất cả nút khác.

Đường đi ngắn nhất mọi cặp (All-Pairs Shortest Paths - Floyd-Warshall)

Ban đầu ma trận đầu ra giống ma trận chi phí của đồ thị. Sau đó cập nhật ma trận với mọi đỉnh k làm đỉnh trung gian.

Độ phức tạp thời gian: O(V³), V là số đỉnh.

Đầu vào − Ma trận chi phí đồ thị:

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 đường đi ngắn nhất mọi cặp:

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(cost)

Đầu vào − Ma trận chi phí đồ thị.

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

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
    hiển thị ma trận cost hiện tại
End

Ví dụ (C++)

#include 
#include 
#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

Đầ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