Bellman-Ford — Chiến binh cạnh âm

Dijkstra nhanh, nhưng gục ngã trước trọng số âm. Trong thế giới thực, trọng số âm xuất hiện thường xuyên hơn bạn nghĩ: tỷ giá ngoại tệ sau khi lấy logarithm, chi phí giảm khi đi qua đối tác chiến lược, hoặc latency bù trừ trong network routing. Bellman-Ford sinh ra để xử lý chính xác các tình huống này.

Ngoài shortest path, Bellman-Ford còn có khả năng Dijkstra không bao giờ có: phát hiện chu trình âm — yếu tố quyết định trong bài toán forex arbitrage, nơi một vòng giao dịch tạo ra lợi nhuận vô hạn.

Bức tranh tư duy

Hình dung bạn đang thương lượng giá vé máy bay. Mỗi vòng đàm phán, bạn hỏi tất cả hãng bay: "Nếu tôi bay qua anh, có rẻ hơn không?". Sau đủ $V - 1$ vòng (vì đường bay dài nhất có tối đa $V - 1$ chặng), bạn chắc chắn tìm được giá rẻ nhất.

Nhưng nếu sau vòng thứ $V$ mà giá vẫn giảm — có nghĩa tồn tại một "vòng lặp ma thuật" mà đi càng nhiều càng rẻ. Đó chính là chu trình âm.

Vòng 1:  Relaxation → một số dist[] cải thiện
Vòng 2:  Relaxation → thêm dist[] cải thiện
  ...
Vòng V-1: Relaxation → tất cả shortest path đã ổn định
Vòng V:   Relaxation → vẫn cải thiện? → 🚨 CHU TRÌNH ÂM!

Cốt lõi kỹ thuật

Nguyên lý hoạt động

Bellman-Ford lặp $V - 1$ lần, mỗi lần duyệt tất cả cạnh và thực hiện relaxation. Tại sao $V - 1$ ? Vì đường đi ngắn nhất trong đồ thị $V$ đỉnh không có chu trình âm có tối đa $V - 1$ cạnh. Sau lần lặp thứ $k$ , thuật toán đảm bảo tìm được shortest path có tối đa $k$ cạnh.

Cài đặt chuẩn

C++PythonJavaGo

cpp

#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

// Returns: {dist[], hasNegativeCycle}
pair<vector<int>, bool> bellmanFord(int V, const vector<Edge>& edges, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    // Phase 1: V-1 relaxations
    for (int i = 0; i < V - 1; ++i) {
        bool updated = false;
        for (const auto& e : edges) {
            if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break; // Early termination
    }

    // Phase 2: Detect negative cycle
    for (const auto& e : edges) {
        if (dist[e.u] != INT_MAX && dist[e.u] + e.w < dist[e.v]) {
            return {dist, true}; // Negative cycle exists
        }
    }

    return {dist, false};
}

python

from dataclasses import dataclass

@dataclass
class Edge:
    u: int
    v: int
    w: int

def bellman_ford(V: int, edges: list[Edge], src: int) -> tuple[list[float], bool]:
    """
    Returns: (dist[], has_negative_cycle)
    Time: O(V * E), Space: O(V)
    """
    INF = float('inf')
    dist = [INF] * V
    dist[src] = 0

    # Phase 1: V-1 relaxations
    for i in range(V - 1):
        updated = False
        for e in edges:
            if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
                dist[e.v] = dist[e.u] + e.w
                updated = True
        if not updated:
            break  # Early termination

    # Phase 2: Detect negative cycle
    has_cycle = False
    for e in edges:
        if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
            has_cycle = True
            break

    return dist, has_cycle

java

import java.util.*;

public class BellmanFord {
    static int[] dist;
    static boolean hasNegativeCycle;

    public static void bellmanFord(int V, int[][] edges, int src) {
        dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int i = 0; i < V - 1; i++) {
            boolean updated = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        hasNegativeCycle = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                hasNegativeCycle = true;
                break;
            }
        }
    }
}

import "math"

type Edge struct{ U, V, W int }

func bellmanFord(V int, edges []Edge, src int) ([]int, bool) {
    const INF = math.MaxInt32
    dist := make([]int, V)
    for i := range dist {
        dist[i] = INF
    }
    dist[src] = 0

    for i := 0; i < V-1; i++ {
        updated := false
        for _, e := range edges {
            if dist[e.U] != INF && dist[e.U]+e.W < dist[e.V] {
                dist[e.V] = dist[e.U] + e.W
                updated = true
            }
        }
        if !updated {
            break
        }
    }

    for _, e := range edges {
        if dist[e.U] != INF && dist[e.U]+e.W < dist[e.V] {
            return dist, true // Negative cycle
        }
    }
    return dist, false
}

Phát hiện chu trình âm

Sau $V - 1$ vòng, nếu vẫn có cạnh relax được → tồn tại chu trình âm. Truy vết bằng cách đi ngược prev[] từ đỉnh vừa relax:

python

def find_negative_cycle(V: int, edges: list[Edge], src: int) -> list[int] | None:
    INF = float('inf')
    dist = [INF] * V
    prev = [-1] * V
    dist[src] = 0

    for i in range(V - 1):
        for e in edges:
            if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
                dist[e.v] = dist[e.u] + e.w
                prev[e.v] = e.u

    # Tìm đỉnh trong chu trình âm
    cycle_node = -1
    for e in edges:
        if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
            cycle_node = e.v
            break

    if cycle_node == -1:
        return None

    # Đi ngược V lần để chắc chắn rơi vào chu trình
    cur = cycle_node
    for _ in range(V):
        cur = prev[cur]

    # Truy vết chu trình
    cycle = []
    start = cur
    cycle.append(start)
    cur = prev[cur]
    while cur != start:
        cycle.append(cur)
        cur = prev[cur]
    cycle.append(start)
    cycle.reverse()

    return cycle

SPFA — Tối ưu thực tế

Shortest Path Faster Algorithm (SPFA) là biến thể Bellman-Ford dùng queue: chỉ relaxation từ đỉnh vừa được cập nhật, thay vì duyệt toàn bộ cạnh mỗi vòng. Average case nhanh hơn đáng kể, nhưng worst case vẫn $O (V \times E)$ .

python

from collections import deque

def spfa(V: int, adj: list[list[tuple[int, int]]], src: int) -> tuple[list[float], bool]:
    """adj[u] = [(v, weight), ...]. Returns (dist[], has_negative_cycle)."""
    INF = float('inf')
    dist = [INF] * V
    in_queue = [False] * V
    relax_count = [0] * V
    dist[src] = 0

    q = deque([src])
    in_queue[src] = True

    while q:
        u = q.popleft()
        in_queue[u] = False

        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                relax_count[v] += 1
                if relax_count[v] >= V:
                    return dist, True  # Negative cycle
                if not in_queue[v]:
                    q.append(v)
                    in_queue[v] = True

    return dist, False

Thực chiến

Tình huống: Phát hiện Forex Arbitrage

Bối cảnh: Sàn giao dịch ngoại tệ có N đồng tiền với bảng tỷ giá. Cần phát hiện cơ hội arbitrage — một chuỗi đổi tiền mà sau khi quay về đồng ban đầu, số tiền tăng.

Mục tiêu: Tìm chu trình arbitrage nếu tồn tại.

Ý tưởng: Chuyển phép nhân tỷ giá thành phép cộng bằng logarithm. Chu trình có tích > 1 ↔ tổng log > 0 ↔ tổng (-log) < 0 ↔ chu trình âm trong Bellman-Ford.

python

import math
from dataclasses import dataclass

@dataclass
class Edge:
    u: int
    v: int
    w: float

def detect_arbitrage(currencies: list[str],
                     rates: list[list[float]]) -> list[str] | None:
    """
    Phát hiện cơ hội arbitrage trong bảng tỷ giá.
    rates[i][j] = tỷ giá đổi từ currency i sang j.
    Returns: chuỗi arbitrage nếu tìm thấy, None nếu không.
    """
    n = len(currencies)
    edges = []
    for i in range(n):
        for j in range(n):
            if i != j and rates[i][j] > 0:
                edges.append(Edge(i, j, -math.log(rates[i][j])))

    # Chạy Bellman-Ford từ mỗi nguồn
    for src in range(n):
        dist = [float('inf')] * n
        prev = [-1] * n
        dist[src] = 0

        for _ in range(n - 1):
            for e in edges:
                if dist[e.u] + e.w < dist[e.v]:
                    dist[e.v] = dist[e.u] + e.w
                    prev[e.v] = e.u

        # Kiểm tra chu trình âm
        for e in edges:
            if dist[e.u] + e.w < dist[e.v]:
                # Truy vết chu trình
                cur = e.v
                for _ in range(n):
                    cur = prev[cur]

                cycle = []
                start = cur
                cycle.append(currencies[start])
                cur = prev[cur]
                while cur != start:
                    cycle.append(currencies[cur])
                    cur = prev[cur]
                cycle.append(currencies[start])
                cycle.reverse()
                return cycle

    return None

Phân tích: Time $O (N^{3})$ — chạy Bellman-Ford ( $O (N \times N^{2})$ ) từ mỗi nguồn. Trong thực tế, chỉ cần chạy từ 1 nguồn nếu đồ thị tỷ giá liên thông. Các hệ thống trading production chạy thuật toán này mỗi khi tỷ giá cập nhật (vài millisecond) để phát hiện cơ hội arbitrage trước đối thủ.

Sai lầm điển hình

❌ Sai lầm 1: Relaxation từ đỉnh có dist = INF

Vấn đề: Không kiểm tra dist[u] != INF trước khi relaxation.

python

# SAI: relaxation từ đỉnh unreachable
for e in edges:
    if dist[e.u] + e.w < dist[e.v]:  # INF + w có thể overflow!
        dist[e.v] = dist[e.u] + e.w

Tại sao sai: Trong C++/Java, INT_MAX + w gây integer overflow → giá trị âm → relaxation sai. Trong Python, float('inf') + w = inf nên ít nguy hiểm hơn, nhưng vẫn nên kiểm tra cho consistency.

python

# ĐÚNG: kiểm tra dist[u] trước
for e in edges:
    if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
        dist[e.v] = dist[e.u] + e.w

❌ Sai lầm 2: Dùng V vòng thay vì V-1

Vấn đề: Lặp V lần thay vì V-1 lần trong phase 1.

python

# SAI: V vòng → lẫn lộn phase 1 và phase 2
for i in range(V):       # Phải là V-1!
    for e in edges:
        ...

Tại sao sai: Vòng thứ V chính là vòng detect chu trình âm. Nếu gộp vào phase 1, thuật toán có thể tiếp tục relaxation qua chu trình âm → dist[] sai.

python

# ĐÚNG: V-1 vòng relaxation, sau đó kiểm tra riêng
for i in range(V - 1):  # Phase 1
    for e in edges:
        ...
# Phase 2: check V-th iteration separately

❌ Sai lầm 3: Kết luận "không có shortest path" khi phát hiện chu trình âm

Vấn đề: Tìm thấy chu trình âm → bỏ toàn bộ kết quả.

Tại sao sai: Chu trình âm chỉ ảnh hưởng đến các đỉnh reachable từ chu trình đó. Các đỉnh không nằm trên hoặc sau chu trình vẫn có shortest path hợp lệ. Cần xác định chính xác đỉnh nào bị ảnh hưởng.

python

# ĐÚNG: chỉ đánh dấu đỉnh bị ảnh hưởng bởi negative cycle
affected = [False] * V
for e in edges:
    if dist[e.u] != INF and dist[e.u] + e.w < dist[e.v]:
        # BFS/DFS từ e.v để đánh dấu tất cả đỉnh reachable
        mark_affected(e.v, adj, affected)

Under the Hood

Hiệu năng

Aspect	Complexity	Ghi chú
Time (worst case)	$O (V \times E)$	V-1 vòng × E cạnh mỗi vòng
Time (best case)	$O (E)$	Early termination nếu không có cập nhật
SPFA (average)	$O (E)$ ~ $O (k E)$	k nhỏ trên thực tế, nhưng worst case vẫn $O (V E)$
Space	$O (V)$	Mảng dist[] và prev[]

Nội bộ triển khai

Tại sao V-1 vòng là đủ? Đường đi ngắn nhất không có chu trình âm đi qua tối đa V đỉnh → tối đa V-1 cạnh. Sau vòng lặp thứ $k$ , thuật toán tìm được shortest path dùng tối đa $k$ cạnh. Sau V-1 vòng, tất cả shortest path đã được tìm.

SPFA vs Bellman-Ford thuần: SPFA dùng queue chỉ xét đỉnh vừa cập nhật, giảm số relaxation thừa. Trên random graph, SPFA nhanh hơn đáng kể. Nhưng có thể bị "đánh bại" bởi đồ thị đặc biệt (ví dụ: grid graph) khiến worst case xuất hiện. Trong competitive programming, SPFA thường bị TLE trên test case cố tình anti-SPFA.

So sánh với Dijkstra:

Tiêu chí	Dijkstra (binary heap)	Bellman-Ford
Time	$O ((V + E) \log V)$	$O (V \times E)$
Trọng số âm	❌	✅
Chu trình âm	❌	✅ Phát hiện được
Cài đặt	Phức tạp hơn (heap)	Đơn giản (3 vòng for)
Distributed system	Khó	✅ Tự nhiên (distance vector routing)

Trade-offs

Bellman-Ford phù hợp cho distributed systems vì mỗi node chỉ cần biết neighbor trực tiếp — không cần global topology. BGP (Border Gateway Protocol) — giao thức routing backbone của Internet — dựa trên nguyên lý Bellman-Ford (distance vector routing).

Nhược điểm: $O (V E)$ chậm hơn Dijkstra trên đồ thị lớn không có trọng số âm. Với đồ thị sparse ( $E \approx V$ ), Bellman-Ford là $O (V^{2})$ — chấp nhận được. Với dense graph ( $E \approx V^{2}$ ), $O (V^{3})$ — cân nhắc Floyd-Warshall nếu cần all-pairs.

Checklist ghi nhớ

✅ Checklist triển khai

Khi nào dùng Bellman-Ford

[ ] Đồ thị có cạnh trọng số âm → bắt buộc (Dijkstra sẽ sai)
[ ] Cần phát hiện chu trình âm → Bellman-Ford là lựa chọn tự nhiên nhất
[ ] Distributed routing (mỗi node chỉ biết neighbor) → distance vector protocol

Khi code

[ ] Phase 1: đúng $V - 1$ vòng (không phải V, không phải E)
[ ] Kiểm tra dist[u] != INF trước khi relaxation (tránh overflow)
[ ] Early termination: break nếu không có cập nhật trong một vòng
[ ] Phase 2: vòng thứ V riêng biệt để detect negative cycle

Tối ưu

[ ] Cân nhắc SPFA nếu cần tốc độ trung bình tốt hơn (nhưng worst case không đổi)
[ ] Nếu không có trọng số âm → dùng Dijkstra thay vì Bellman-Ford
[ ] Nếu cần all-pairs → cân nhắc Floyd-Warshall (đơn giản hơn V lần Bellman-Ford)

Bài tập luyện tập

Bài 1: Shortest Path với cạnh âm — Foundation

Đề bài: Cho đồ thị có hướng V đỉnh, E cạnh (có thể có trọng số âm). Tìm khoảng cách ngắn nhất từ đỉnh 0 đến tất cả đỉnh khác. In "NEGATIVE CYCLE" nếu tồn tại chu trình âm reachable từ nguồn.

Input: V=5, E=8
Edges: (0,1,-1), (0,2,4), (1,2,3), (1,3,2), (1,4,2), (3,2,5), (3,1,1), (4,3,-3)

Output: [0, -1, 2, -2, 1]

🧠 Quiz

Câu hỏi: Bellman-Ford cần bao nhiêu vòng relaxation tối đa để đảm bảo tìm shortest path (không có chu trình âm)?

[ ] A. V vòng
[x] B. V-1 vòng
[ ] C. E vòng
[ ] D. V × E vòng Giải thích: Đường ngắn nhất không chu trình đi qua tối đa V đỉnh, tức tối đa V-1 cạnh. Sau vòng lặp thứ $k$ , thuật toán tìm được shortest path dùng ≤ $k$ cạnh. Do đó V-1 vòng là đủ.

💡 Gợi ý

Xây danh sách cạnh, khởi tạo dist
V-1 vòng relaxation + early termination
Vòng V để kiểm tra negative cycle

✅ Lời giải

python

def solve(V, edges, src=0):
    INF = float('inf')
    dist = [INF] * V
    dist[src] = 0

    for i in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return "NEGATIVE CYCLE"

    return dist

Phân tích: Time $O (V \times E)$ , Space $O (V)$ . Early termination giúp best case chỉ cần 1 vòng.

Bài 2: Currency Arbitrage — Intermediate

Đề bài: Cho N đồng tiền và bảng tỷ giá. Xác định có tồn tại cơ hội arbitrage (chuỗi đổi tiền quay về đồng ban đầu với lợi nhuận > 0) hay không.

💡 Gợi ý

Chuyển phép nhân thành phép cộng: weight = -log(rate)
Arbitrage ↔ tích tỷ giá > 1 ↔ tổng -log(rate) < 0 ↔ chu trình âm
Dùng Bellman-Ford detect negative cycle

✅ Lời giải

python

import math

def has_arbitrage(n: int, rates: list[list[float]]) -> bool:
    dist = [0.0] * n  # Khởi tạo 0 để detect từ mọi nguồn

    for i in range(n - 1):
        for u in range(n):
            for v in range(n):
                if u != v and rates[u][v] > 0:
                    w = -math.log(rates[u][v])
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w

    for u in range(n):
        for v in range(n):
            if u != v and rates[u][v] > 0:
                w = -math.log(rates[u][v])
                if dist[u] + w < dist[v]:
                    return True

    return False

Phân tích: Time $O (N^{3})$ (N đỉnh, $N^{2}$ cạnh). Khởi tạo dist = 0 cho tất cả đỉnh để không cần chạy từ nhiều nguồn.

Liên kết học tiếp

Từ khóa glossary: Bellman-Ford, shortest path, negative edge, negative cycle, relaxation, SPFA, distance vector, forex arbitrage

Tìm kiếm liên quan: thuật toán Bellman-Ford, đường đi ngắn nhất cạnh âm, phát hiện chu trình âm, SPFA algorithm

Bellman-Ford — Chiến binh cạnh âm ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Nguyên lý hoạt động ​

Cài đặt chuẩn ​

Phát hiện chu trình âm ​

SPFA — Tối ưu thực tế ​

Thực chiến ​

Tình huống: Phát hiện Forex Arbitrage ​

Sai lầm điển hình ​

❌ Sai lầm 1: Relaxation từ đỉnh có dist = INF ​

❌ Sai lầm 2: Dùng V vòng thay vì V-1 ​

❌ Sai lầm 3: Kết luận "không có shortest path" khi phát hiện chu trình âm ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Shortest Path với cạnh âm — Foundation ​

Bài 2: Currency Arbitrage — Intermediate ​

Liên kết học tiếp ​

Bellman-Ford — Chiến binh cạnh âm

Bức tranh tư duy

Cốt lõi kỹ thuật

Nguyên lý hoạt động

Cài đặt chuẩn

Phát hiện chu trình âm

SPFA — Tối ưu thực tế

Thực chiến

Tình huống: Phát hiện Forex Arbitrage

Sai lầm điển hình

❌ Sai lầm 1: Relaxation từ đỉnh có dist = INF

❌ Sai lầm 2: Dùng V vòng thay vì V-1

❌ Sai lầm 3: Kết luận "không có shortest path" khi phát hiện chu trình âm

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Shortest Path với cạnh âm — Foundation

Bài 2: Currency Arbitrage — Intermediate

Liên kết học tiếp