Thuật toán Floyd-Warshall

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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ướngcạnh mang trọng số dươ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ích[sửa | sửa mã nguồn]

Có thể hiểu 1 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 O(n^3) để 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-Warshall[sửa | sửa mã nguồn]

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ánO(n^2). 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ánO(n^3).

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 trong số âm.

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

Tham khảo[sửa | sửa mã nguồn]