1677155
Thuật toán Floyd–Warshall
https://vi.wikipedia.org/wiki?curid=1677155
Title: Thuật toán Floyd–Warshall
 dist["v"]["v"] ← 0
 đối với "k" từ 1 đến |V|
 đối với "i" từ 1 đến |V|
 đối với "j" từ 1 đến |V|
 nếu dist["i"]["j"] &gt; dist["i"]["k"] + dist["k"]["j"] 
 dist["i"]["j"] ← dist["i"]["k"] + dist["k"]["j"]
 kết thúc nếu
Ví dụ.
Thuật toán trên được thực hiện trên đồ thị ở bên trái trong hình dưới đây:
Trước lần duyệt đệ quy đầu tiên của vòng lặp ngoài, gán ở trên, các đường đi được biết chỉ tương ứng với các cạnh đơn trong đồ thị. Tại , đường đi đi qua đỉnh 1 được tìm thấy: cụ thể là đường đi [2,1,3] được tìm thấy, thay thế đường đi [2,3] có ít cạnh hơn nhưng lại dài hơn (về trọng số). Tại , đường đi đi qua các đỉnh {1,2} được tìm thấy. Các ô màu đỏ và xanh dương cho thấy cách mà đường đi [4,2,1,3] được ghép từ hai đường đi đã biết [4,2] và [2,1,3] gặp trong các lần lặp trước, với 2 trong giao điểm. Đường đi [4,2,3] không được xem xét, vì [2,1,3] là đường đi ngắn nhất gặp từ 2 đến 3. Tại , đường đi qua các đỉnh {1,2,3} được tìm thấy. Cuối cùng, tại , tất cả các đường đi ngắn nhất được tìm thấy.
Ma trận khoảng cách ở mỗi lần lặp của , với các khoảng cách được cập nhật được in đậm, sẽ là:
So sánh giữa 2 thuật toán dijkstra và Floyd-Warshall.
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 là formula_44.
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 là formula_45.