Thuật toán Floyd–Warshall

Những cuốn atlas đường bộ ngày xưa có một bảng ở cuối sách: khoảng cách giữa mọi cặp thành phố. Floyd–Warshall là cách tính một bảng như thế, và là một trong những thuật toán ngắn nhất từng được viết: ba vòng lặp, một phép so sánh, và mọi khoảng cách ngắn nhất đều vào đúng chỗ.

Một đồ thị nhỏ có các cạnh mang độ dài, bên cạnh là bảng khoảng cách giữa mọi cặp đỉnh, với một hàng và một cột được tô sáng
Một đồ thị nhỏ có các cạnh mang độ dài, bên cạnh là bảng khoảng cách giữa mọi cặp đỉnh, với một hàng và một cột được tô sáng

Ý tưởng

Thuật toán Dijkstra và Bellman–Ford tìm khoảng cách ngắn nhất từ một điểm xuất phát. Floyd–Warshall tìm chúng từ mọi đỉnh đến mọi đỉnh khác cùng một lúc, trong một bảng mỗi đỉnh một hàng và một cột. Nó bắt đầu từ những gì các cạnh cho biết trực tiếp, rồi cải thiện cả bảng bằng cách cho phép ngày càng nhiều đỉnh làm điểm trung gian trên đường đi.

Từng bước

Điền bảng: 0 từ mỗi đỉnh đến chính nó, độ dài cạnh giữa hai đỉnh kề nhau, và vô cùng ở chỗ khác. Sau đó, với mỗi đỉnh k, và với mọi cặp i, j: nếu khoảng cách từ i đến k cộng khoảng cách từ k đến j nhỏ hơn khoảng cách từ i đến j, ghi số nhỏ hơn vào. Đó là toàn bộ thuật toán. Trong mã, đó là ba vòng lặp, với k ở ngoài cùng.

Một ví dụ

Lấy bốn đỉnh với các cạnh A–B dài 3, B–C dài 1, A–C dài 5 và C–D dài 2. Bảng bắt đầu với các cạnh đó, và vô cùng cho A–D và B–D. Vòng A không thay đổi gì, vì mọi đường qua A đều dài hơn. Vòng B tìm thấy A đến C qua B: 3 + 1 = 4, ngắn hơn 5. Vòng C tìm thấy A đến D qua C: 4 + 2 = 6, và B đến D: 1 + 2 = 3, cả hai đều là đường đầu tiên tìm được. Vòng D không thay đổi gì. Bảng cuối cùng: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Vì sao thứ tự các vòng lặp quan trọng

Điểm trung gian k phải là vòng lặp ngoài cùng. Sau vòng của k, mỗi ô là khoảng cách ngắn nhất khi chỉ dùng k đỉnh đầu tiên làm điểm trung gian, và vòng tiếp theo xây trên đó: đường đi tốt nhất qua điểm trung gian mới là đường đi tốt nhất đến nó cộng đường đi tốt nhất từ nó, cả hai đều đã đúng. Đặt k ở vòng lặp trong sẽ phá vỡ bảo đảm này và có thể để lại khoảng cách sai. Cập nhật bảng ngay tại chỗ trong một vòng là an toàn, vì hàng và cột của chính k không thay đổi trong vòng đó.

Lịch sử và ứng dụng

Bernard Roy mô tả phương pháp này năm 1959. Năm 1962, Stephen Warshall công bố nó cho bao đóng bắc cầu, bài toán chỉ hỏi một đỉnh có đến được đỉnh khác hay không, còn Robert Floyd công bố nó cho đường đi ngắn nhất. Nó tính bảng khoảng cách và bảng định tuyến, tìm đường kính của một mạng, cho biết đỉnh nào đến được đỉnh nào, và khi có một ô âm trên đường chéo thì phát hiện ra chu trình âm.

Khám phá

Mở ứng dụng và nhấn Bước. Đồ thị ở một bên và bảng ở bên kia. Mỗi vòng tô sáng hàng và cột của điểm trung gian hiện tại; mỗi bước ghi khoảng cách ngắn hơn của một cặp và viền hai ô đã được cộng. Các ô thay đổi trong vòng này được tô màu. Chọn điểm xuất phát và đích để xem đường đi ngắn nhất giữa chúng khi bảng đã hoàn tất.

Câu hỏi thường gặp

Độ phức tạp thời gian của Floyd–Warshall là bao nhiêu?

O(n³) với n đỉnh, bất kể số cạnh, và bộ nhớ O(n²) cho bảng. Đây là phương pháp được ưu tiên cho đồ thị nhỏ hoặc dày, nơi vòng lặp đơn giản của nó chạy rất nhanh.

Floyd–Warshall hay chạy Dijkstra từ mọi đỉnh?

Với đồ thị dày, hoặc khi cạnh có thể âm, Floyd–Warshall đơn giản hơn và nhanh gần như vậy. Với đồ thị lớn và thưa có cạnh không âm, chạy thuật toán Dijkstra từ mỗi đỉnh sẽ nhanh hơn.

Floyd–Warshall có phải là quy hoạch động không?

Có. Nó giải bài toán cho các đường đi có điểm trung gian nằm trong k đỉnh đầu tiên bằng lời giải cho k − 1 đỉnh đầu tiên, và chỉ giữ một bảng, ghi đè lên trong lúc chạy.

Bao đóng bắc cầu là gì?

Bảng cho biết đỉnh nào đến được đỉnh nào, bỏ qua khoảng cách. Phiên bản thuật toán của Warshall tính nó bằng "or" và "and" thay cho "min" và "+".

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử Floyd–Warshall