Bellman-Ford — Negative weight, detect negative cycle

Lesson 05 cho thấy Dijkstra fail khi graph có edge â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: node = đơn vị tiền tệ, edge weight = -log(rate). Nếu tồn tại một chu trình với tổng weight â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 edge, 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ó edge â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 correct trên graph có edge â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.

1. Init dist[start] = 0, dist[v] = infinity cho moi v khac.
2. Lap V-1 lan:
   For moi edge (u, v, w):
      If dist[u] + w < dist[v]:
         dist[v] = dist[u] + w
         parent[v] = u
3. V-th iteration: neu van relax duoc -> co negative cycle.

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 edge 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 weight âm.

3. Code Java

import java.util.*;

public class BellmanFord {
    record Edge(int from, int to, int weight) {}

    // Returns dist[] from start to every vertex.
    // Throws IllegalStateException if a negative cycle is reachable from start.
    public static int[] bellmanFord(int n, List<Edge> edges, int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // V-1 relaxation rounds
        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (Edge e : edges) {
                // Guard: skip unreachable vertices to avoid MAX_VALUE overflow
                if (dist[e.from()] == Integer.MAX_VALUE) continue;

                if (dist[e.from()] + e.weight() < dist[e.to()]) {
                    dist[e.to()] = dist[e.from()] + e.weight();
                    updated = true;
                }
            }
            if (!updated) break; // early termination: converged before V-1 rounds
        }

        // V-th iteration: detect negative cycle
        for (Edge e : edges) {
            if (dist[e.from()] != Integer.MAX_VALUE
                    && dist[e.from()] + e.weight() < dist[e.to()]) {
                throw new IllegalStateException("Negative cycle detected");
            }
        }

        return dist;
    }
}

3.1 Trace ví dụ — graph 4 đỉnh với edge âm

Graph directed weighted:

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

Edges: 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 edge â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→1→2 cost 3 trước, nhưng Bellman-Ford tìm được path cost 1 qua vòng lặp.

4. 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ó edge âm. Với graph không có edge â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.

5. So sánh Bellman-Ford vs Dijkstra

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

Negative cycle là chu trình có tổng weight âm. Nếu vertex 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 weight âm = negative cycle = arbitrage.

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.

7. Currency arbitrage — code minh họa

import java.util.*;

public class CurrencyArbitrage {
    // currencies: 0=USD, 1=EUR, 2=JPY, 3=GBP
    // edge weight = -log(exchange_rate)
    // negative cycle = arbitrage opportunity

    public static boolean detectArbitrage(int n, double[][] rates) {
        // Build edge list: -log(rate[i][j]) for each pair
        List<double[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && rates[i][j] > 0) {
                    edges.add(new double[]{i, j, -Math.log(rates[i][j])});
                }
            }
        }

        double[] dist = new double[n];
        // Start from a virtual source connected to all nodes with weight 0
        Arrays.fill(dist, 0.0);

        // V-1 relaxation rounds
        for (int k = 0; k < n - 1; k++) {
            for (double[] e : edges) {
                int u = (int) e[0], v = (int) e[1];
                double w = e[2];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        // V-th iteration: detect negative cycle
        for (double[] e : edges) {
            int u = (int) e[0], v = (int) e[1];
            double w = e[2];
            if (dist[u] + w < dist[v]) {
                return true; // arbitrage opportunity found
            }
        }
        return false;
    }
}

8. SPFA — Shortest Path Faster Algorithm

Insight: Bellman-Ford relax mọi edge mỗi vòng dù nhiều vertex 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ừ vertex vừa được update:

// SPFA: only process vertices whose dist was recently updated
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(start);
boolean[] inQueue = new boolean[n];
inQueue[start] = true;
int[] count = new int[n]; // count enqueue times for negative cycle detection

while (!queue.isEmpty()) {
    int u = queue.poll();
    inQueue[u] = false;

    for (Edge e : adj.get(u)) {
        if (dist[u] == Integer.MAX_VALUE) continue;
        if (dist[u] + e.weight() < dist[e.to()]) {
            dist[e.to()] = dist[u] + e.weight();
            if (!inQueue[e.to()]) {
                queue.offer(e.to());
                inQueue[e.to()] = true;
                // If a vertex is enqueued n times, it's in a negative cycle
                if (++count[e.to()] >= n) {
                    throw new IllegalStateException("Negative cycle detected");
                }
            }
        }
    }
}

Vì sao count[v] >= n 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 vertex chỉ cần enqueue nhiều nhất V-1 lần. Nếu một vertex đã enqueue n 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 vertex đề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.

9. Pitfall tổng hợp

Pitfall 1 — Quên V-th iteration check:

// BUG: algorithm returns result without checking for negative cycle
for (int i = 0; i < n - 1; i++) {
    for (Edge e : edges) {
        if (dist[e.from()] != Integer.MAX_VALUE
                && dist[e.from()] + e.weight() < dist[e.to()]) {
            dist[e.to()] = dist[e.from()] + e.weight();
        }
    }
}
// MISSING: V-th iteration check
return dist; // dist[] has garbage values if negative cycle exists

Nếu graph có negative cycle, dist tiếp tục thay đổi qua mỗi vòng — không hội tụ. Consumer nhận dist[] sai hoàn toàn. Luôn chạy V-th iteration check.

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

// BUG: Integer.MAX_VALUE + negative weight overflows to large positive
for (Edge e : edges) {
    // dist[e.from()] = Integer.MAX_VALUE, e.weight() = -5
    // MAX_VALUE + (-5) = MAX_VALUE - 5, still huge -> no update. OK?
    // But: MAX_VALUE + 1 = MIN_VALUE (overflow) -> wrong comparison!
    if (dist[e.from()] + e.weight() < dist[e.to()]) { // overflow risk
        dist[e.to()] = dist[e.from()] + e.weight();
    }
}

// CORRECT: guard unreachable vertices
if (dist[e.from()] == Integer.MAX_VALUE) continue;
if (dist[e.from()] + e.weight() < dist[e.to()]) { ... }

Với int, Integer.MAX_VALUE + 1 overflow thành Integer.MIN_VALUE — 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 weight được sắp xếp để mọi vertex đề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.

10. Ứ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. Edge weight = 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 edge weight = -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 edge i → j weight 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).

11. Deep Dive

12. 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ó edge â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ó edge â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 edge weight -log(rate).

13. Tự kiểm tra

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