Thuật toán Floyd–Warshall

Trong khoa học máy tính, thuật toán Floyd-Warshall (còn được gọi là thuật toán Floyd, thuật toán Roy-Warshall, thuật toán Roy-Floyd hoặc thuật toán WFI) là một thuật toán để tìm đường đi ngắn nhất trong đồ thị có hướng đồ thị có trọng số với trọng số cạnh 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 (trọng số tổng hợp) của đường đi ngắn nhất giữa mọi cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường đi, có thể khôi phục các đường đi với sửa đổi đơn giản cho thuật toán. Các phiên bản của thuật toán cũng có thể được sử dụng để tìm bao đóng chuyển tiếp của quan hệ formula_1, hoặc (liên quan đến phương pháp bỏ phiếu Schulze) đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị có trọng số.
Lịch sử và tên gọi.
Thuật toán Floyd–Warshall là một ví dụ về quy hoạch động, và được xuất bản dưới dạng hiện nay của nó bởi Robert Floyd vào năm 1962. Tuy nhiên, nó về cơ bản giống như các thuật toán trước đó được xuất bản bởi Bernard Roy vào năm 1959 và cũng bởi Stephen Warshall vào năm 1962 để tìm bao đóng chuyển tiếp của một đồ thị, và có liên quan chặt chẽ với thuật toán của Kleene (xuất bản vào năm 1956) để chuyển đổi một tự động hóa hữu hạn xác định thành một biểu thức chính quy. Định dạng hiện đại của thuật toán dưới dạng ba vòng lặp lồng nhau được mô tả đầu tiên bởi Peter Ingerman, cũng vào năm 1962.
Thuật toán.
Thuật toán Floyd–Warshall so sánh nhiều đường đi khả dĩ trong đồ thị giữa mỗi cặp đỉnh. Nó được đảm bảo để tìm tất cả các đường đi ngắn nhất và có thể làm điều này với formula_2 so sánh trong một đồ thị, mặc dù có thể có formula_3 cạnh trong đồ thị. Nó làm như vậy bằng cách tăng dần ước tính đường đi ngắn nhất giữa hai đỉnh, cho đến khi ước tính tối ưu.
Xét đồ thị formula_4 với đỉnh formula_5 đánh số từ 1 đến formula_6. Hãy xem xét hàm formula_7 trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ formula_8 đến formula_9 sử dụng các đỉnh chỉ từ tập formula_10 làm điểm trung gian trong đường đi. Giờ đây, với hàm này, mục tiêu của chúng ta là tìm độ dài của đường đi ngắn nhất từ mỗi formula_8 đến từng formula_9 sử dụng bất kỳ đỉnh nào trong formula_13. Theo định nghĩa, đây là giá trị formula_14, mà chúng ta sẽ tìm đệ quy.
Chú ý rằng formula_7 phải nhỏ hơn hoặc bằng formula_16: sẽ linh hoạt hơn nếu được phép sử dụng đỉnh formula_17. Nếu formula_7 thực sự nhỏ hơn formula_16, thì phải có một đường đi từ formula_8 đến formula_9 sử dụng các đỉnh formula_10 mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh formula_17. Đường đi này có thể được phân rã thành:
Và dĩ nhiên, chúng phải là các đường đi ngắn nhất như vậy, nếu không chúng ta có thể làm giảm độ dài hơn nữa. Nói cách khác, chúng ta đã đến công thức đệ quy:
Trong khi đó, trường hợp cơ sở được đưa ra bởi
ở đó formula_34 biểu thị trọng số của cạnh từ formula_8 đến formula_9 nếu tồn tại và ∞ (vô cùng) trong trường hợp khác.
Các công thức này là trọng tâm của thuật toán Floyd-Warshall. Thuật toán hoạt động bằng cách tính formula_7 cho tất cả các cặp formula_38 với formula_39, sau đó là formula_40, sau đó là formula_41, vân vân. Quá trình này tiếp tục cho đến khi formula_42, và chúng ta đã tìm thấy đường đi ngắn nhất cho tất cả các cặp formula_38 sử dụng bất kỳ đỉnh trung gian nào. Mã giả cho phiên bản cơ bản này là:
Mã giả.
 cho dist là một mảng |V| × |V| của khoảng cách tối thiểu khởi tạo thành ∞ (vô cùng)
 đối với mỗi cạnh ("u", "v") thực hiện
 dist["u"]["v"] ← w("u", "v") "// Trọng số của cạnh ("u", "v")"
 đối với mỗi đỉnh "v" thực hiện
 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.