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.

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
EndVí 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