Thuật toán Bellman–Ford
Một số bài toán đường đi ngắn nhất có những cạnh làm đường đi rẻ hơn: một khoản hoàn tiền, một đoạn xuống dốc, một tỷ giá có lợi cho bạn. Thuật toán Dijkstra không xử lý được chúng. Thuật toán Bellman–Ford thì được, bằng cách đổi sự khéo léo lấy sự kiên nhẫn.
Ý tưởng
Mọi thuật toán đường đi ngắn nhất đều dựa vào một thao tác, nới lỏng một cạnh: nếu đi đến u rồi theo cạnh u → v ngắn hơn đường tốt nhất đã biết đến v, hãy dùng nó. Thuật toán Dijkstra nới lỏng mỗi cạnh một lần, theo một thứ tự khéo léo chỉ đúng khi không có cạnh âm. Bellman–Ford không giả định như vậy. Nó nới lỏng mọi cạnh, theo một thứ tự cố định bất kỳ, hết lần này đến lần khác, cho đến khi khoảng cách thôi thay đổi.
Từng bước
Gán cho điểm xuất phát khoảng cách 0 và mọi đỉnh khác vô cùng. Lặp lại n − 1 lần, với n đỉnh: duyệt mọi cạnh u → v và nới lỏng nó nếu u có khoảng cách. Dừng sớm nếu cả một lượt không thay đổi gì. Rồi chạy thêm một lượt nữa. Nếu vẫn còn cạnh nới lỏng được, có một chu trình với tổng âm đến được từ điểm xuất phát; nếu không, mọi khoảng cách đều ngắn nhất, và các đỉnh đã ghi nhớ cho ra các đường đi.
Một ví dụ
Lấy các cạnh một chiều A → B dài 4, A → C 5, B → D 2 và C → B −3, xét theo thứ tự đó, từ A. Lượt 1 cho B 4, C 5 và D 6, rồi C → B giảm B xuống 5 − 3 = 2. Lượt 2 giảm D xuống 2 + 2 = 4. Lượt 3 không thay đổi gì, nên đáp án là B 2, C 5, D 4. Thuật toán Dijkstra sẽ cố định B ở 4 và D ở 6 trước khi thấy cạnh âm. Thêm cạnh D → C dài −4, và chu trình C → B → D → C có tổng −5: mỗi lượt lại giảm các khoảng cách, và lượt kiểm tra sẽ báo cáo điều đó.
Vì sao n − 1 lượt là đủ
Một đường đi ngắn nhất, nếu tồn tại, không bao giờ lặp lại đỉnh, nên có tối đa n − 1 cạnh. Nới lỏng mọi cạnh trong một lượt sẽ kéo dài mỗi đường đi ngắn nhất đã biết đúng thêm một cạnh, bất kể thứ tự các cạnh. Vì vậy sau lượt k, mọi đường đi ngắn nhất có đến k cạnh đều đúng, và sau n − 1 lượt thì tất cả đều đúng. Thứ tự vẫn ảnh hưởng đến tốc độ: một thứ tự tốt có thể xong trong một hai lượt.
Lịch sử và ứng dụng
Alfonso Shimbel mô tả phương pháp này năm 1955, Lester Ford Jr. năm 1956, Edward F. Moore năm 1957 và Richard Bellman năm 1958; thuật toán mang tên hai người trong số đó, Bellman và Ford. Mỗi bộ định tuyến có thể tự chạy các lượt của nó, nên nó trở thành nền tảng của các giao thức định tuyến vectơ khoảng cách như RIP. Trong tài chính, lấy logarit âm của tỷ giá sẽ biến một vòng giao dịch tiền tệ có lời (kinh doanh chênh lệch giá) thành một chu trình âm, và Bellman–Ford có thể tìm ra nó.
Khám phá
Mở ứng dụng và nhấn Bước. Mọi cạnh đều một chiều, và một số độ dài là âm. Mỗi bước xét một cạnh, theo thứ tự cố định, và các ô hiển thị lượt hiện tại cùng số khoảng cách mà lượt đó đã thay đổi. Thường thì sớm có một lượt không thay đổi gì và quá trình tìm kiếm dừng sớm. Đánh dấu Thêm chu trình âm và xem các khoảng cách giảm qua từng lượt cho đến khi lượt kiểm tra tìm ra chu trình và vẽ nó màu đỏ.
Câu hỏi thường gặp
Độ phức tạp thời gian của Bellman–Ford là bao nhiêu?
O(V · E) với V đỉnh và E cạnh: tối đa V − 1 lượt, mỗi lượt xét mọi cạnh. Với việc dừng sớm, trong thực tế nó thường nhanh hơn nhiều, và trong trường hợp tốt nhất chỉ cần một lượt.
Chu trình âm là gì?
Một chu trình có tổng độ dài các cạnh nhỏ hơn không. Đi vòng quanh nó hết lần này đến lần khác làm đường đi ngắn bao nhiêu tùy ý, nên khoảng cách ngắn nhất đến mọi đỉnh đến được qua nó đều không xác định.
Bellman–Ford có dùng được trên đồ thị vô hướng không?
Chỉ khi không có cạnh âm: một cạnh âm vô hướng có thể đi tới đi lui, và đó đã là một chu trình âm gồm hai cạnh. Với cạnh không âm thì nó dùng được, nhưng thuật toán Dijkstra nhanh hơn.
SPFA là gì?
Shortest Path Faster Algorithm, một phiên bản của Bellman–Ford chỉ xét lại các cạnh đi ra từ những đỉnh vừa thay đổi khoảng cách, nhờ một hàng đợi. Nó thường nhanh hơn nhiều, dù trường hợp xấu nhất vẫn như cũ.
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ử Bellman–Ford