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ệ , 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  so sánh trong một đồ thị, mặc dù có thể có  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ị  với đỉnh  đánh số từ 1 đến . Hãy xem xét hàm  trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ  đến  sử dụng các đỉnh chỉ từ tập  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  đến từng  sử dụng bất kỳ đỉnh nào trong . Theo định nghĩa, đây là giá trị , mà chúng ta sẽ tìm đệ quy.

Chú ý rằng  phải nhỏ hơn hoặc bằng : sẽ linh hoạt hơn nếu được phép sử dụng đỉnh . Nếu  thực sự nhỏ hơn , thì phải có một đường đi từ  đến  sử dụng các đỉnh  mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh . Đường đi này có thể được phân rã thành:

(1) một đường đi từ  đến  sử dụng các đỉnh , kế tiếp là

(2) một đường đi từ  đến  sử dụng các đỉ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

ở đó  biểu thị trọng số của cạnh từ  đến  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  cho tất cả các cặp  với , sau đó là , sau đó là , vân vân. Quá trình này tiếp tục cho đến khi , và chúng ta đã tìm thấy đường đi ngắn nhất cho tất cả các cặp  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] > 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:

600px

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à:
+ 1  2  3  4 1 0  ∞  −2  ∞ 2 4  0  3  ∞ 3 ∞  ∞  0  2 4 ∞  −1  ∞  0

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

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

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

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

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à .
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à .

  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

Chú thích

Thể loại:Bài toán thời gian đa thức
Thể loại:Giải thuật định tuyến
Thể loại:Giải thuật lý thuyết đồ thị
Thể loại:Tối ưu hóa tổ hợp
Thể loại:Quy hoạch động