Bellman-Ford — Negative weight, detect negative cycle

TL;DR: Bellman-Ford tìm shortest path trên weighted graph bằng cách relax tất cả E cạnh V-1 lần — đảm bảo đúng kể cả khi có cạnh âm, điều mà Dijkstra không làm được. Vòng lặp thứ V (sau V-1) phát hiện negative cycle: nếu vẫn còn cạnh có thể relax, có chu trình tổng âm khiến dist giảm mãi. Pitfall lớn nhất: quên kiểm tra vòng V-th — algorithm im lặng trả về dist[] không hội tụ, consumer dùng giá trị sai mà không biết.

Lesson 05 — Dijkstra cho thấy Dijkstra fail khi graph có cạnh âm — greedy invariant sụp đổ ngay khi xuất hiện một shortcut âm sau lúc finalize. Bài toán thực tế: currency arbitrage. Mô hình hóa thị trường forex thành graph: đỉnh = đơn vị tiền tệ, trọng số cạnh = -log(rate). Nếu tồn tại một chu trình với tổng trọng số âm, ta vừa tìm được một vòng đổi tiền mang lại lợi nhuận — arbitrage opportunity. Dijkstra không xử lý được graph kiểu này.

Bài này dạy Bellman-Ford: V-1 iteration relax mọi cạnh, detect negative cycle bằng V-th iteration, RIP routing protocol, currency arbitrage.

1. Analogy — Thử mọi đường liên tục

Dijkstra là người greedy: luôn đi theo "con đường gần nhất chưa đi" trước. Với graph không có cạnh âm, điều đó là optimal. Nhưng nếu có shortcut âm xuất hiện sau khi đã finalize một đỉnh, greedy 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 shortest path có thể có (không qua cycle) đã được tìm ra — vì bất kỳ simple path nào cũng có tối đa V-1 cạnh.

Tradeoff: Bellman-Ford chậm hơn đáng kể (O(V × E) vs 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: shortest simple path có tối đa V-1 cạnh. Sau vòng lặp thứ k, ta đảm bảo dist[v] chứa shortest path từ start đến v đ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à đủ?

Shortest simple path không có cycle — nên có tối đa V-1 cạnh. Sau vòng lặp k, bất kỳ shortest path nào dùng nhiều nhất k cạnh đã được tính đúng trong dist[]. Sau V-1 vòng, tất cả shortest paths (kể cả path dài nhất có V-1 cạnh) đã hội tụ.

Vì sao V-th iteration detect negative cycle?

Nếu sau V-1 vòng vẫn còn cạnh có thể relax — nghĩa là tồn tại "path ngắn hơn" sử dụng V cạnh. Path với V cạnh trên V đỉnh bắt buộc phải đi qua một đỉnh hai lần — tức có cycle. Nếu path đó ngắn hơn, cycle đó có tổng trọng số âm.

flowchart TD
    INIT["Khởi tạo: dist[start]=0\ndist[v]=INF cho mọi v khác"]
    LOOP["Vòng lặp i = 1 đến V-1"]
    RELAX["Relax mỗi cạnh (u->v, w):\nnếu dist[u] + w < dist[v]:\n    cập nhật dist[v]"]
    EARLY{"Không có\ncập nhật nào?"}
    DONE_EARLY["Đã hội tụ sớm\n→ dừng"]
    VTH["Vòng V-th:\nkiểm tra negative cycle"]
    CYCLE{"Vẫn relax\nđược?"}
    ERROR["Báo lỗi:\nnegative cycle"]
    RETURN["Trả về dist[], parent[]"]

    INIT --> LOOP
    LOOP --> RELAX
    RELAX --> EARLY
    EARLY -- "có" --> DONE_EARLY
    EARLY -- "không" --> LOOP
    DONE_EARLY --> VTH
    LOOP -- "xong V-1 vòng" --> VTH
    VTH --> CYCLE
    CYCLE -- "có" --> ERROR
    CYCLE -- "không" --> RETURN

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

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.

Đây là trường hợp Dijkstra cho kết quả sai: Dijkstra sẽ finalize 0→2 = 4 sớm hơn, bỏ qua path 0→1→2 tốt hơn vì cạnh âm xuất hiện sau.

3. Complexity

O(V × E) từ đâu? V-1 vòng lặp, mỗi vòng duyệt toàn bộ E cạnh để relax → V × E operations.

Khi nào chọn Bellman-Ford thay Dijkstra? Chỉ khi graph có cạnh âm. Với graph không có cạnh âm, Dijkstra luôn nhanh hơn đáng kể. Nếu graph có negative cycle, Bellman-Ford detect được còn Dijkstra sẽ cho kết quả sai hoặc loop.

4. So sánh Bellman-Ford vs Dijkstra

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

Negative cycle là chu trình có tổng trọng số âm. Nếu đỉnh v reachable từ negative cycle, thì không tồn tại shortest path đến v — ta có thể đi vòng quanh cycle vô hạn lần, giảm total 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 = negative cycle = arbitrage.

graph LR
    USD["USD"] -- "-log(1.08)" --> EUR["EUR"]
    EUR -- "-log(130.5)" --> JPY["JPY"]
    JPY -- "-log(0.0082)" --> USD

Thực tế, arbitrage tồn tại trong microseconds — market makers điều chỉnh ngay sau khi phát hiện. High-frequency trading system phát hiện bằng Bellman-Ford trên graph tiền tệ, execute trong microseconds trước khi opportunity biến mất.

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

Insight: Bellman-Ford relax mọi cạnh mỗi vòng dù nhiều đỉnh không thay đổi. Nếu dist[u] không thay đổi, relax các cạnh từ u là vô nghĩa.

SPFA chỉ relax từ đỉnh vừa được update:

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 detect negative cycle? Mỗi lần v được enqueue là khi dist của nó được cải thiện. Shortest simple path 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. Nếu một đỉnh đã enqueue V lần hoặc nhiều hơn, phải có negative cycle.

Tradeoff SPFA vs Bellman-Ford:

• Average case: SPFA nhanh hơn đáng kể trên sparse graph, empirical thường O(kE) với k nhỏ.
• Worst case: SPFA vẫn O(V × E) — adversarial input khiến mọi đỉnh đều enqueue nhiều lần.
• Production choice: Dùng Bellman-Ford khi cần guaranteed O(V × E) bound. SPFA khi cần performance thực tế và input không adversarial.

8. Pitfall tổng hợp

Pitfall 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 tiếp tục thay đổi qua mỗi vòng — không hội tụ. Luôn chạy V-th iteration check.

Pitfall 2 — Bỏ qua guard dist[u] != INF

-- BUG: dist[u] = INF, w = -5
-- INF + (-5) có thể overflow thành số âm lớn -> so sánh sai hoàn toàn
for each cạnh (u -> v, w):
    if dist[u] + w < dist[v]:    -- overflow risk 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 kiểu số nguyên, INF + 1 overflow thành số âm rất lớn — so sánh nhỏ hơn mọi giá trị → toàn bộ dist[] bị corrupt. Luôn guard trước khi cộng.

Pitfall 3 — Tin SPFA "luôn nhanh hơn Bellman-Ford"

SPFA có worst case O(V × E) giống hệt Bellman-Ford. Với adversarial input (ví dụ: graph dạng grid với trọng số được sắp xếp để mọi đỉnh đều được enqueue nhiều lần), SPFA không nhanh hơn. Production code cần guaranteed bound nên dùng Bellman-Ford chuẩn; SPFA tốt cho competitive programming nhưng không phải luôn đúng cho production.

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

RIP (Routing Information Protocol): distributed Bellman-Ford. Mỗi router duy trì một bảng khoảng cách (distance vector) đến mọi router khác và broadcast cho neighbors. Neighbor nhận bảng → relax: nếu đi qua router A đến B ngắn hơn đường đang biết → cập nhật. Quá trình hội tụ sau V-1 vòng broadcast. Trọng số cạnh = hop count (RIP giới hạn tối đa 15 hop để tránh count-to-infinity). OSPF (lesson 05) dùng Dijkstra tập trung hơn — nhanh hơn nhưng cần mỗi router biết toàn bộ topology.

Currency arbitrage detection: forex traders, financial exchange system. Graph tiền tệ với trọng số cạnh = -log(rate). Negative cycle = arbitrage. High-frequency trading system chạy Bellman-Ford liên tục (hoặc SPFA) để detect opportunity trong microseconds.

Game theory — Reinforcement learning MDPs: value iteration trong reinforcement learning có structure tương tự: relax từng state theo Bellman equation. Không giống hệt Bellman-Ford nhưng cùng ý tưởng iterative relaxation hội tụ đến optimal value.

Constraint solver — Difference constraints: hệ bất đẳng thức x_j - x_i <= w_ij có thể biểu diễn thành graph với cạnh i → j trọng số w_ij. Bellman-Ford giải hệ này (tìm assignment thỏa mãn tất cả ràng buộc). Nếu tìm thấy negative cycle → hệ infeasible (không có assignment nào thỏa mãn).

10. Deep Dive

11. Tóm tắt

• Bellman-Ford tìm shortest path bằng cách relax tất cả E cạnh V-1 lần — đảm bảo đúng kể cả khi có cạnh âm.
• V-1 vòng đủ vì shortest simple path có tối đa V-1 cạnh; sau vòng k, shortest path dùng nhiều nhất k cạnh đã hội tụ.
• V-th iteration detect negative cycle: nếu vẫn còn cạnh có thể relax, có path V-cạnh tốt hơn → phải có cycle âm.
• Guard dist[u] != INF trước khi cộng để tránh integer overflow gây corrupt toàn bộ dist[].
• Complexity O(V × E) — chậm hơn Dijkstra; chỉ dùng khi graph có cạnh âm.
• SPFA cải thiện average case bằng queue, nhưng worst case vẫn O(V × E) — không thay thế Bellman-Ford cho guaranteed bound.
• RIP routing là distributed Bellman-Ford: mỗi router relax dựa trên bảng của neighbors.
• Currency arbitrage mô hình hóa thành negative cycle detection trên forex graph với trọng số cạnh -log(rate).

12. Tự kiểm tra

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