Cấu trúc dữ liệu và Giải thuật Bài 49: Xử lý trọng số âm và chu trình âm với Thuật toán Bellman-Ford.

Thuật toán Dijkstra sụp đổ hoàn toàn khi mạng lưới xuất hiện những con đường mang trọng số âm (Negative Weights). Tư duy lòng tham (Greedy) của Dijkstra tự động chốt hạ khoảng cách ngắn nhất ngay khi lấy một đỉnh ra khỏi Min-Heap, vì nó đinh ninh rằng việc đi tiếp chỉ làm chi phí tăng lên. Nếu đi đường vòng mà lại được "trả thêm tiền" (chi phí âm), Dijkstra sẽ vĩnh viễn bỏ lỡ con đường tối ưu đó.

Để đối phó với thế giới tài chính hoặc các hệ thống mạng phức tạp nơi trọng số có thể mang giá trị âm, Richard Bellman và Lester Ford đã thiết kế một thuật toán từ bỏ hoàn toàn lòng tham, chuyển sang một chiến thuật càn lướt toàn diện.

1. Nguyên lý Nới lỏng (Relaxation) và Giới hạn V-1

Thay vì dùng Min-Heap để dò dẫm từng đỉnh một cách thông minh, Bellman-Ford chọn cách cục súc nhưng chắc chắn tuyệt đối: Duyệt qua TOÀN BỘ các cạnh của đồ thị, cập nhật lại khoảng cách, và lặp lại quá trình này $V - 1$ lần (với $V$ là số lượng Đỉnh).

Tại sao lại là $V - 1$ lần?

Trong một đồ thị không có chu trình (vòng lặp vô tận), con đường đi từ đỉnh $A$ đến đỉnh $B$ dài nhất cũng chỉ đi qua tối đa $V - 1$ cạnh. Bằng cách càn lướt toàn bộ các cạnh $V - 1$ lần, thuật toán đảm bảo mọi thông tin về các con đường ngắn nhất (dù là đường vòng có trọng số âm) đều được lan truyền (propagate) đến mọi ngóc ngách của đồ thị.

Quá trình "thấy đường rẻ hơn thì cập nhật" này được gọi là Relaxation (Nới lỏng).

2. Chu trình âm: Lỗ đen của Đồ thị

Chuyện gì xảy ra nếu Đồ thị tồn tại một Chu trình âm (Negative Cycle)?

Giả sử có 3 đỉnh $A, B, C$ nối vòng tròn với nhau, và tổng trọng số của vòng tròn này là $-5$. Cứ mỗi lần bạn đi hết một vòng, chi phí lại giảm đi 5. Hệ thống sẽ rơi vào một vòng lặp vô cực để bào mòn chi phí xuống Âm Vô Cực ($-\infty$). Không tồn tại "đường đi ngắn nhất" trong một đồ thị chứa chu trình âm.

Bellman-Ford sở hữu một ma thuật để phát hiện "lỗ đen" này:

Sau khi đã lặp đủ $V - 1$ lần (đảm bảo mọi đường đi hợp lệ đều đã tối ưu), thuật toán chạy thêm 1 vòng lặp cuối cùng (vòng thứ $V$). Nếu ở vòng này mà vẫn có một con đường tiếp tục được "nới lỏng" (chi phí tiếp tục giảm), điều đó chứng minh chắc chắn 100% đồ thị đang chứa một chu trình âm. Hệ thống lập tức báo lỗi và dừng lại.

3. Triển khai Bellman-Ford bằng Golang

Khác với Dijkstra cần Danh sách kề phức tạp, Bellman-Ford chỉ cần một mảng phẳng chứa tất cả các Cạnh (Edge List), khiến việc lập trình backend vô cùng đơn giản.

Go

import "math"

// Chỉ cần lưu danh sách các cạnh, không cần Danh sách kề
type Edge struct {
    From, To, Weight int
}

// Hàm trả về mảng khoảng cách và một cờ báo Chu trình âm
func BellmanFord(vertices int, edges []Edge, start int) ([]int, bool) {
    distances := make([]int, vertices)
    for i := range distances {
        distances[i] = math.MaxInt32
    }
    distances[start] = 0 // Đỉnh xuất phát

    // Bước 1: Quét toàn bộ cạnh (V - 1) lần
    for i := 0; i < vertices-1; i++ {
        for _, edge := range edges {
            // Nới lỏng (Relax) nếu tìm thấy đường đi rẻ hơn
            if distances[edge.From] != math.MaxInt32 && distances[edge.From]+edge.Weight < distances[edge.To] {
                distances[edge.To] = distances[edge.From] + edge.Weight
            }
        }
    }

    // Bước 2: Vòng lặp thứ V để phát hiện Chu trình âm
    for _, edge := range edges {
        if distances[edge.From] != math.MaxInt32 && distances[edge.From]+edge.Weight < distances[edge.To] {
            // Chi phí vẫn tiếp tục giảm -> Dính chu trình âm!
            return nil, true 
        }
    }

    return distances, false
}

• Thời gian thực thi: $O(V \times E)$. So với tốc độ $O((V+E)\log V)$ của Dijkstra, Bellman-Ford chậm hơn rất nhiều, nên nó chỉ được kích hoạt khi hệ thống chắc chắn có trọng số âm.

• Không gian (RAM): $O(V)$, cực kỳ tiết kiệm bộ nhớ.

4. Ứng dụng: Hạt nhân của Forex Arbitrage

Bellman-Ford là công cụ tối thượng trong hai lĩnh vực hệ thống lõi:

1. Săn chênh lệch tỷ giá hối đoái (Forex Arbitrage): Khi quy đổi tiền tệ vòng quanh (Ví dụ: USD $\rightarrow$ EUR $\rightarrow$ JPY $\rightarrow$ USD), đôi khi tỷ giá thị trường bị lệch, khiến bạn kết thúc chu trình với số USD lớn hơn ban đầu. Các Trading Bot biến tỷ giá thành logarit âm (Negative Logarithm) để tạo ra đồ thị trọng số âm. Sau đó, chúng chạy Bellman-Ford liên tục. Nếu hàm trả về true (có chu trình âm), một cơ hội kiếm tiền Arbitrage không rủi ro vừa xuất hiện.

2. Giao thức định tuyến RIP (Routing Information Protocol): Các Router thế hệ cũ sử dụng thuật toán Distance-Vector dựa trên nguyên lý Bellman-Ford để trao đổi bảng định tuyến định kỳ cho nhau, dần dần hội tụ (converge) ra con đường ngắn nhất trên mạng diện rộng (WAN).

Việc tìm đường đi ngắn nhất chỉ là một khía cạnh của bài toán mạng lưới. Nếu bài toán yêu cầu bạn phải dùng hệ thống cáp quang để nối tất cả các ga Metro Line 1 lại với nhau sao cho tổng độ dài dây cáp là rẻ nhất (không tạo ra vòng lặp thừa), chúng ta sẽ bước sang nhóm thuật toán xây dựng Cây khung (Spanning Tree).