Thuật toán Floyd–Warshall

(đổi hướng từ Thuật toán Floyd-Warshall)

Thuật toán Floyd–Warshall còn được gọi là thuật toán Floyd được Robert Floyd tìm ra năm 1962.thuật toán Floyd là một thuật toán giải quyết bài toán đường đi ngắn nhất trong một đồ thị có hướng dựa trên khái niệm các Đỉnh Trung Gian.

Bài toán: Xét đồ thị có hướng có trọng số G=<V,E>:

Tập đỉnh: V={v1, v2, …, vn}
Ma trận khoảng cách: W = (i, j)

Thuật toán Floyd–Warshall giúp xác định tất cả các Đường đi ngắn nhất giữa tất cả các cặp đỉnh.

Định lý: Thuật toán Floyd–Warshall cho ta Ma trận W* = Wn là ma trận Khoảng cách nhỏ nhất của đồ thị G.

Chú thíchSửa đổi

Có thể hiểu một cách đơn giản. Để đi từ a --> b. Bạn mất 1 quãng đường là x.
Thuật toán sẽ tìm 1 đường đi gián tiếp từ a -- k -- b và nếu đường đi này ngắn hơn đường đi trực tiếp thì ta gán luôn giá trị nhỏ nhất của đường đi trực tiếp bằng đường đi gián tiếp.
Thuật toán Floyd cần   để giải Bài toán đường đi ngắn nhất cho mỗi cặp đỉnh.

So sánh giữa 2 thuật toán dijkstra và Floyd-WarshallSửa đổi

Thuật toán Dijkstra bình thường có 2 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán . Thuật toán Floyd–Warshall bình thường có 3 vòng lặp lồng nhau sẽ có Độ phức tạp thuật toán .

Dijsktra
Floyd-Warshall
Ưu điểm Chi phí thấp hơn Thuật toán Floyd–Warshall Không cần chạy lại Thuật toán (có nghĩa là có tính kế thừa từ đường đi lẫn nhau)

Có thể chạy được với trọng số âm.

Nhược điểm Không chạy được với trọng số âm. Chi phí cao   cho mỗi cặp đỉnh

Tham khảoSửa đổi