Bellman-Ford — Negative weight, detect negative cycle

TL;DR: Bellman-Ford tìm đường ngắn nhất trên weighted graph bằng cách relax (thử cải thiện) tất cả E cạnh, lặp V-1 lần. Nhờ vậy nó đúng kể cả khi có cạnh âm, điều Dijkstra không làm được. Vòng thứ V (sau V-1 vòng) dùng để phát hiện negative cycle: nếu vẫn còn cạnh relax được thì có chu trình tổng âm làm dist giảm mãi. Bẫy lớn nhất: quên kiểm tra vòng V-th, khi đó thuật toán lặng lẽ trả về dist[] chưa hội tụ và nơi dùng nó nhận giá trị sai mà không hay biết.

Bài Dijkstra cho thấy Dijkstra sai khi graph có cạnh âm: lý lẽ greedy sụp đổ ngay khi có một đường tắt âm xuất hiện sau lúc đã chốt đỉnh. Bài toán thực tế là currency arbitrage (kiếm lời nhờ chênh lệch tỷ giá). Ta mô hình thị trường forex thành graph: đỉnh là đơn vị tiền tệ, trọng số cạnh là -log(rate). Nếu có một chu trình với tổng trọng số âm, tức là ta vừa tìm được một vòng đổi tiền có lời. Dijkstra không xử lý được graph kiểu này.

Bài này dạy Bellman-Ford: relax mọi cạnh qua V-1 vòng, phát hiện negative cycle bằng vòng thứ V, cùng giao thức routing RIP và currency arbitrage.

1. Hình dung: Thử mọi đường liên tục

Dijkstra là người tham lam: luôn đi theo "con đường gần nhất chưa đi" trước. Với graph không có cạnh âm, cách đó cho kết quả tối ưu. Nhưng nếu có đường tắt âm xuất hiện sau khi đã chốt một đỉnh, cách tham lam này thua.

Bellman-Ford là người kiên nhẫn: mỗi vòng, thử relax tất cả các cạnh trong graph. Sau V-1 vòng, mọi đường ngắn nhất có thể có (không qua cycle) đều đã được tìm ra, vì một simple path (path không lặp đỉnh) bất kỳ có tối đa V-1 cạnh.

Đánh đổi: Bellman-Ford chậm hơn đáng kể (O(V × E) so với O((V+E) log V)), nhưng đúng trên graph có cạnh âm.

2. Thuật toán — V-1 iteration

Ý tưởng cốt lõi: simple path ngắn nhất có tối đa V-1 cạnh. Sau vòng lặp thứ k, dist[v] chắc chắn chứa đường ngắn nhất từ start đến v trong số các đường đi qua nhiều nhất k cạnh.

BellmanFord(G, start):
    dist[v] <- INF cho mọi v != start
    dist[start] <- 0
    parent[v] <- NIL cho mọi v

    -- V-1 vòng relax toàn bộ cạnh
    for i <- 1 đến V-1:
        updated <- false
        for each cạnh (u -> v, trọng số w) trong G:
            if dist[u] = INF: continue       -- u chưa thể tới được, bỏ qua
            if dist[u] + w < dist[v]:
                dist[v] <- dist[u] + w
                parent[v] <- u
                updated <- true
        if not updated: break                -- đã hội tụ sớm, dừng

    -- Vòng V-th: phát hiện negative cycle
    for each cạnh (u -> v, trọng số w) trong G:
        if dist[u] != INF and dist[u] + w < dist[v]:
            báo lỗi "Phát hiện negative cycle"

    return dist, parent

Time: O(V×E) Space: O(V)

Vì sao V-1 vòng là đủ?

Simple path ngắn nhất không có cycle, nên có tối đa V-1 cạnh. Sau vòng lặp k, mọi đường ngắn nhất dùng nhiều nhất k cạnh đã được tính đúng trong dist[]. Sau V-1 vòng, tất cả đường ngắn nhất (kể cả đường dài nhất có V-1 cạnh) đã hội tụ, tức không đổi nữa.

Vì sao vòng thứ V phát hiện được negative cycle?

Nếu sau V-1 vòng vẫn còn cạnh relax được, nghĩa là có một path ngắn hơn dùng V cạnh. Path V cạnh trên V đỉnh buộc phải đi qua một đỉnh hai lần, tức có cycle. Bỏ cycle đó đi sẽ còn path không quá V-1 cạnh, mà path này không tốt bằng, nên cycle bị bỏ phải có tổng trọng số âm.

2.1 Trace ví dụ — graph 4 đỉnh với cạnh âm

Bảng dưới là một bảng trace, mỗi dòng một vòng, cột là các biến; chưa quen thì ôn Bảng trace.

Graph directed weighted:

0 ---(3)--> 1
|           |
(4)       (-2)
|           v
+--------> 2 ---(1)--> 3

Cạnh: 0→1 w3, 0→2 w4, 1→2 w(-2), 2→3 w1.

Kết quả: dist = [0, 3, 1, 2]. Shortest path 0→2 là 0→1→2 với cost 1 (đi qua cạnh âm -2), không phải 0→2 trực tiếp cost 4.

Với ví dụ nhỏ này Dijkstra tình cờ vẫn ra đúng, vì đỉnh 1 (dist 3) được chốt trước đỉnh 2 (dist 4). Phản ví dụ khiến Dijkstra sai thật là graph A→B 1, A→C 3, C→B -5 ở bài Dijkstra.

3. Complexity

O(V × E) từ đâu ra? V-1 vòng lặp, mỗi vòng duyệt toàn bộ E cạnh để relax, tổng cỡ V × E thao tác. Đây là hai vòng for lồng nhau, đếm giống bài Lặp lồng nhau: số lần lặp ngoài nhân số lần lặp trong.

Khi nào chọn Bellman-Ford thay Dijkstra? Chỉ khi graph có cạnh âm. Graph không có cạnh âm thì Dijkstra luôn nhanh hơn hẳn. Nếu graph có negative cycle, Bellman-Ford phát hiện được còn Dijkstra cho kết quả sai hoặc lặp mãi.

4. So sánh Bellman-Ford vs Dijkstra

Bảng ở mục 1 đã so sánh hai thuật toán. Thêm một điểm: Dijkstra dùng được trên bản đồ và OSPF nhờ nhanh, Bellman-Ford dùng cho routing kiểu RIP và arbitrage nhờ chịu được trọng số âm và chạy được theo kiểu phân tán.

5. Negative cycle — ý nghĩa thực tế

Negative cycle là chu trình có tổng trọng số âm. Nếu từ negative cycle đi tới được đỉnh v thì không tồn tại đường ngắn nhất đến v, vì ta có thể đi vòng quanh cycle mãi để giảm tổng cost mãi.

Currency arbitrage: đổi USD → EUR → JPY → USD và thu về nhiều USD hơn ban đầu. Nếu rate(USD→EUR) × rate(EUR→JPY) × rate(JPY→USD) > 1 thì -log(rate_1) + (-log(rate_2)) + (-log(rate_3)) < 0. Tổng trọng số âm nghĩa là có negative cycle, và đó chính là cơ hội arbitrage.

Với tỷ giá giả định trong hình, tích là 1,08 × 130,5 × 0,0082 ≈ 1,156, lớn hơn 1, nên có lời. Ngoài thị trường thật, chênh lệch như vậy biến mất rất nhanh vì giá tự điều chỉnh, và phí giao dịch thường ăn hết phần lời nhỏ, nên đây chủ yếu là một ví dụ mô hình hoá hơn là công thức kiếm tiền.

Thử ngẫmđổi trọng số cạnh thành -log(rate) để arbitrage (tích tỷ giá > 1) trở thành negative cycle (tổng log < 0). Nếu tích ba tỷ giá đúng bằng 1 thì Bellman-Ford báo gì?

6. Currency arbitrage — pseudocode minh họa

-- currencies: 0=USD, 1=EUR, 2=JPY, 3=GBP
-- trọng số cạnh = -log(tỷ giá[i][j])
-- negative cycle = arbitrage opportunity

detectArbitrage(n, rates):
    -- Xây edge list từ bảng tỷ giá
    edges <- []
    for i <- 0 đến n-1:
        for j <- 0 đến n-1:
            if i != j and rates[i][j] > 0:
                edges.append((i, j, -log(rates[i][j])))

    -- Khởi tạo dist = 0 cho mọi đỉnh (virtual source với weight 0)
    dist[v] <- 0 cho mọi v

    -- V-1 vòng relax
    for k <- 1 đến n-1:
        for each (u, v, w) trong edges:
            if dist[u] + w < dist[v]:
                dist[v] <- dist[u] + w

    -- Vòng V-th: phát hiện negative cycle
    for each (u, v, w) trong edges:
        if dist[u] + w < dist[v]:
            return true    -- tìm thấy arbitrage opportunity

    return false

Time: O(V×E) Space: O(V)

7. SPFA — Shortest Path Faster Algorithm

Ý tưởng: Bellman-Ford relax mọi cạnh ở mỗi vòng dù nhiều đỉnh không đổi. Nếu dist[u] không đổi thì relax các cạnh xuất phát từ u là vô ích.

SPFA chỉ relax từ những đỉnh vừa được cập nhật:

SPFA(G, start):
    dist[v] <- INF cho mọi v != start
    dist[start] <- 0
    inQueue[v] <- false cho mọi v
    count[v] <- 0                  -- đếm số lần enqueue để detect cycle

    Q <- Queue rỗng
    Q.enqueue(start)
    inQueue[start] <- true

    while Q không rỗng:
        u <- Q.dequeue()
        inQueue[u] <- false

        for each cạnh (u -> v, trọng số w):
            if dist[u] = INF: continue
            if dist[u] + w < dist[v]:
                dist[v] <- dist[u] + w
                if not inQueue[v]:
                    Q.enqueue(v)
                    inQueue[v] <- true
                    count[v] <- count[v] + 1
                    -- đỉnh được enqueue >= V lần -> có negative cycle
                    if count[v] >= V:
                        báo lỗi "Negative cycle"

Time worst-case: O(V×E) Space: O(V)

Vì sao count[v] >= V báo hiệu negative cycle? Mỗi lần v được enqueue là lúc dist của nó được cải thiện. Simple path ngắn nhất có tối đa V-1 cạnh nên một đỉnh chỉ cần enqueue nhiều nhất V-1 lần. Đỉnh nào đã enqueue V lần trở lên thì chắc chắn có negative cycle.

SPFA so với Bellman-Ford, đánh đổi ra sao:

• Trường hợp trung bình: SPFA thường nhanh hơn rõ trên nhiều input thực tế, nhưng không có chặn trên nào chặt hơn O(V × E).
• Trường hợp xấu nhất: SPFA vẫn O(V × E), vì input cố tình dựng sẵn có thể khiến mọi đỉnh bị enqueue nhiều lần.
• Chọn gì trong thực tế: dùng Bellman-Ford khi cần đảm bảo chặn trên O(V × E); dùng SPFA khi cần tốc độ thực tế và input không bị cố tình dựng để làm khó.

Thử ngẫmSPFA dùng count[v] >= V để phát hiện negative cycle, cùng lập luận là simple path ngắn nhất có tối đa V-1 cạnh. Nếu graph do người dùng gửi lên và không đáng tin, bạn chọn SPFA hay Bellman-Ford thuần?

8. Bẫy tổng hợp

Bẫy 1: Quên V-th iteration check

-- BUG: trả về kết quả mà không kiểm tra negative cycle
for i <- 1 đến V-1:
    for each cạnh (u -> v, w):
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] <- dist[u] + w

return dist    -- dist[] có giá trị sai nếu tồn tại negative cycle
-- Consumer nhận dist[] sai: router chọn đường sai, arbitrage detector báo false

Nếu graph có negative cycle, dist cứ đổi sau mỗi vòng và không hội tụ. Hãy luôn chạy bước kiểm tra ở vòng thứ V.

Bẫy 2: Bỏ qua guard dist[u] != INF

-- BUG: dist[u] = INF (u chưa tới được), w = -5
-- INF + (-5) < INF -> v bị "cải thiện" từ một đỉnh chưa tới được,
-- dist[v] mang giá trị rác gần INF rồi lan tiếp sang các đỉnh khác
for each cạnh (u -> v, w):
    if dist[u] + w < dist[v]:    -- sai khi dist[u] = INF
        dist[v] <- dist[u] + w

-- ĐÚNG: guard trước khi cộng
for each cạnh (u -> v, w):
    if dist[u] = INF: continue   -- u chưa thể tới được, bỏ qua
    if dist[u] + w < dist[v]:
        dist[v] <- dist[u] + w

Với trọng số âm, INF + w nhỏ hơn INF nên so sánh báo "cải thiện" sai; với trọng số dương và kiểu số nguyên, INF + w còn có thể tràn số (overflow). Cả hai đều làm hỏng dist[], nên hãy luôn chặn trước khi cộng.

Bẫy 3: Tin SPFA "luôn nhanh hơn Bellman-Ford"

SPFA có trường hợp xấu nhất O(V × E), giống hệt Bellman-Ford. Với input cố tình dựng (ví dụ graph dạng lưới có trọng số sắp sao cho mọi đỉnh bị enqueue nhiều lần), SPFA không nhanh hơn. Code production cần đảm bảo chặn trên nên dùng Bellman-Ford chuẩn; SPFA hợp với thi lập trình nhưng chưa chắc hợp với production.

9. Ứng dụng thực tế

RIP (Routing Information Protocol): Bellman-Ford chạy phân tán. Mỗi router giữ một bảng khoảng cách (distance vector) đến mọi router khác và gửi cho các router lân cận. Router nhận bảng thì relax: nếu đi qua router A đến B ngắn hơn đường đang biết thì cập nhật. Quá trình hội tụ sau V-1 vòng gửi bảng. Trọng số cạnh là số hop (RIP giới hạn tối đa 15 hop, 16 nghĩa là không tới được, để chặn count-to-infinity, tức khoảng cách cứ tăng dần mãi). OSPF (bài Dijkstra) dùng Dijkstra theo kiểu mỗi router tự tính, thường hội tụ nhanh hơn nhưng mỗi router phải biết toàn bộ topology.

Phát hiện currency arbitrage: dùng ở giao dịch forex và sàn tài chính. Graph tiền tệ với trọng số cạnh là -log(rate), negative cycle chính là arbitrage. Cơ hội thật thường ngắn ngủi và bị phí giao dịch bào mòn, như đã nói ở mục 5.

Giải hệ ràng buộc hiệu (difference constraints): hệ bất đẳng thức x_j - x_i <= w_ij biểu diễn được thành graph với cạnh i → j có trọng số w_ij. Bellman-Ford giải hệ này (tìm bộ giá trị thoả mãn mọi ràng buộc). Nếu gặp negative cycle thì hệ vô nghiệm, không có bộ giá trị nào thoả mãn.

10. Đào sâu

11. Tóm tắt

• Bellman-Ford relax tất cả E cạnh V-1 lần và đúng kể cả khi có cạnh âm; V-1 vòng là đủ vì simple path ngắn nhất có tối đa V-1 cạnh.
• Vòng thứ V phát hiện negative cycle: còn cạnh relax được thì phải có cycle âm.
• Chặn dist[u] != INF trước khi cộng, để INF không bị coi là một khoảng cách thật.
• O(V × E): chậm hơn Dijkstra, chỉ dùng khi graph có cạnh âm. SPFA nhanh hơn trên nhiều input thực tế nhưng xấu nhất vẫn O(V × E).
• Ứng dụng: RIP là Bellman-Ford phân tán; currency arbitrage là tìm negative cycle trên graph -log(rate).

12. Tự kiểm tra

Bài tiếp theo: Floyd-Warshall — all-pairs shortest path