Thuật toán Bellman-Ford là gì: cách hoạt động, code và độ phức tạp

Bellman-Ford giải bài toán gì

Thuật toán Dijkstra nhanh nhưng đòi hỏi trọng số cạnh không âm. Một số bài toán lại có trọng số âm một cách tự nhiên: khoản hoàn tiền, lợi nhuận khi đổi ngoại tệ, hay chi phí năng lượng có thể xuống dưới 0. Bellman-Ford xử lý đúng các đồ thị này và còn cho biết khi nào không tồn tại đường đi ngắn nhất do có chu trình âm, tức một vòng lặp mà bạn có thể đi mãi để chi phí ngày càng nhỏ.

Thuật toán được đặt theo tên Richard Bellman và Lester Ford Jr., những người đã công bố các phiên bản của nó vào thập niên 1950.

Ý tưởng bằng lời đơn giản

1. Đặt khoảng cách của nút xuất phát là 0 và của các nút khác là vô cùng.
2. Lặp lại V − 1 lần: với mỗi cạnh u → v có trọng số w, nếu dist[u] + w < dist[v] thì cập nhật dist[v].
3. Chạy thêm một lượt qua mọi cạnh. Nếu vẫn còn khoảng cách cải thiện được, báo có chu trình âm.

Vì sao cần V − 1 vòng? Đường đi ngắn nhất không chứa chu trình dùng tối đa V − 1 cạnh. Sau vòng thứ k, mọi nút có đường đi ngắn nhất tối đa k cạnh đã có khoảng cách đúng, nên V − 1 vòng bao phủ mọi đường đi đơn.

Ví dụ từng bước

Đồ thị có hướng với 4 nút và các cạnh S→A (4), S→B (5), B→A (−3), A→C (3). Các cạnh được xử lý theo thứ tự này ở mọi vòng.

Ở vòng 1, A trước tiên có giá trị 4 qua S→A, rồi cải thiện xuống 2 qua B→A, và C dùng giá trị đã cải thiện. Thuật toán Dijkstra sẽ chốt A ở giá trị 4 trước khi xét B, đúng là lỗi mà cạnh âm gây ra.

Cài đặt bằng Python

Bellman-Ford làm việc trên một danh sách cạnh đơn giản nên viết rất ngắn:

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

Thêm cạnh C → B có trọng số −6 tạo ra chu trình B → A → C → B với tổng trọng số −3 + 3 − 6 = −6, nên lượt chạy thêm sẽ phát hiện ra nó:

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

Phép kiểm tra dist[u] != INF bỏ qua các cạnh đi ra từ nút chưa tới được. Trong Python, float("inf") + w vẫn là vô cùng nên phép kiểm tra chủ yếu để tiết kiệm công việc. Ở các ngôn ngữ dùng một số nguyên lớn làm vô cùng, nó giúp tránh tràn số và cập nhật sai.

Độ phức tạp thời gian và không gian

Với đồ thị 1.000 nút và 10.000 cạnh, đó là tới khoảng 10 triệu lần nới lỏng, nên Dijkstra nhanh hơn nhiều khi mọi trọng số không âm.

Biến thể và lỗi thường gặp

• Thoát sớm: dừng khi một vòng đầy đủ không thay đổi gì. Cách này an toàn và thường giúp thuật toán nhanh hơn nhiều trong thực tế.
• SPFA (shortest path faster algorithm): chỉ nới lỏng lại các cạnh đi ra từ nút có khoảng cách vừa thay đổi, dùng một hàng đợi. Thường nhanh nhưng trường hợp xấu nhất vẫn là O(V × E).
• Đường đi giới hạn số chặng: chạy đúng k vòng, dùng bản sao khoảng cách của vòng trước, sẽ cho đường đi rẻ nhất có tối đa k cạnh. Cách này giải bài “cheapest flights within k stops”.
• Tìm chính chu trình: giữ bảng nút cha; khi lượt chạy thêm cập nhật nút v, lần theo nút cha V lần để rơi vào bên trong chu trình, rồi đi tiếp cho đến khi quay lại đúng nút đó.

Khi nào dùng và ứng dụng thực tế

• Dùng Bellman-Ford khi trọng số cạnh có thể âm hoặc khi phải phát hiện chu trình âm. Còn lại nên ưu tiên Dijkstra.
• Các giao thức định tuyến vector khoảng cách, như RIP, dùng ý tưởng Bellman-Ford phân tán: mỗi bộ định tuyến liên tục cập nhật ước lượng khoảng cách từ ước lượng của các hàng xóm.
• Kinh doanh chênh lệch tỷ giá (arbitrage): với trọng số bằng -log(rate), một chu trình âm là chuỗi giao dịch đổi tiền kết thúc với nhiều tiền hơn lúc đầu.
• Thuật toán Johnson chạy Bellman-Ford một lần để đặt lại trọng số cho đồ thị, rồi dùng Dijkstra từ mọi nút để tìm đường đi ngắn nhất giữa mọi cặp.
• Ràng buộc hiệu (hệ bất phương trình như x - y <= c) có thể giải bằng đường đi ngắn nhất; chu trình âm nghĩa là hệ vô nghiệm.