floyd-warshall

Thuật toán Floyd–Warshall

Đọc tài liệu này bằng ngôn ngữ khác: Tiếng Anh

Trong khoa học máy tính, thuật toán Floyd–Warshall là một thuật toán dùng để tìm đường đi ngắn nhất trong một đồ thị có trọng số dương hoặc âm (nhưng không có chu trình âm). Một lần thực hiện thuật toán sẽ tìm ra độ d��i (tổng trọng số) của đường đi ngắn nhất giữa tất cả các cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường đi, nhưng có thể tái tạo các đường đi với các thay đổi đơn giản cho thuật toán.

Thuật toán

Thuật toán Floyd–Warshall so sánh tất cả các đường đi có thể qua đồ thị giữa mỗi cặp đỉnh. Nó có thể làm điều này với O(|V|^3) so sánh trong một đồ thị. Điều này đáng chú ý khi xét rằng có thể có tới |V|^2 cạnh trong đồ thị, và mọi tổ hợp cạnh đều được kiểm tra. Nó làm như vậy bằng cách cải thiện dần dần một ước lượng về đường đi ngắn nhất giữa hai đỉnh, cho đến khi ước lượng là tối ưu.

Xem xét một đồ thị G với các đỉnh V được đánh số từ 1 đến N. Xem xét thêm một hàm shortestPath(i, j, k) trả về đường đi ngắn nhất có thể từ i đến j sử dụng chỉ các đỉnh từ tập {1, 2, ..., k} như các điểm trung gian dọc theo đường đi. Bây giờ, với hàm này, mục tiêu của chúng ta là tìm đường đi ngắn nhất từ mỗi i đến mỗi j sử dụng chỉ các đỉnh trong {1, 2, ..., N}.

Công thức này là trái tim của thuật toán Floyd–Warshall.

Ví dụ

Thuật toán trên được thực hiện trên đồ thị bên trái dưới đây:

Trong các bảng dưới đây i là số hàng và j là số cột.

k = 0

	1	2	3	4
1	0	∞	−2	∞
2	4	0	3	∞
3	∞	∞	0	2
4	∞	−1	∞	0

k = 1

	1	2	3	4
1	0	∞	−2	∞
2	4	0	2	∞
3	∞	∞	0	2
4	∞	−	∞	0

k = 2

	1	2	3	4
1	0	∞	−2	∞
2	4	0	2	∞
3	∞	∞	0	2
4	3	−1	1	0

k = 3

	1	2	3	4
1	0	∞	−2	0
2	4	0	2	4
3	∞	∞	0	2
4	3	−1	1	0

k = 4

	1	2	3	4
1	0	−1	−2	0
2	4	0	2	4
3	5	1	0	2
4	3	−1	1	0

Tham khảo

• Wikipedia
• YouTube (bởi Abdul Bari)
• YouTube (bởi Tushar Roy)