Thuật toán Bellman–Ford là gì? Giải thích dễ hiểu kèm demo

Bài viết này giới thiệu ý tưởng thuật toán Bellman–Ford và kèm một demo trực quan bằng JavaScript.

Bellman–Ford giải bài toán gì?

Thuật toán Bellman–Ford giải bài toán:

• Cho một đồ thị có trọng số, có thể chứa cạnh mang trọng số âm.
• Chọn một đỉnh nguồn bắt đầu.
• Tìm khoảng cách ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại.
• Đồng thời có thể phát hiện chu trình âm nếu tồn tại.

Điểm khác biệt lớn so với Dijkstra là Bellman–Ford không yêu cầu trọng số cạnh phải không âm, nên phù hợp trong các bài toán có “chi phí âm” (ví dụ: giảm giá, hoàn tiền, lợi nhuận).

Ý tưởng chính của Bellman–Ford

Bellman–Ford sử dụng kỹ thuật relax cạnh lặp lại nhiều lần:

1. Gán khoảng cách từ nguồn đến chính nó là 0, đến các đỉnh khác là vô cùng.
2. Lặp lại tối đa V - 1 lần (V là số đỉnh):
   • Mỗi lần lặp, duyệt tất cả các cạnh.
   • Nếu đi qua một cạnh giúp giảm khoảng cách đến đỉnh đích, thì cập nhật lại khoảng cách.
3. Sau khi lặp xong, nếu vẫn còn cạnh có thể giảm khoảng cách, chứng tỏ tồn tại chu trình âm.

Vì mỗi lần lặp có thể lan truyền “thông tin khoảng cách” thêm một cạnh, sau tối đa V - 1 lần, mọi đường đi ngắn nhất (không chứa chu trình) đều đã được xét.

Đồ thị dùng trong demo

Để minh họa, sử dụng một đồ thị có trọng số, trong đó có một cạnh mang trọng số âm nhưng không có chu trình âm:

A → B (4)
A → C (2)
B → C (3)
B → D (2)
B → E (3)
C → B (1)
C → D (4)
C → E (5)
D → E (-1)
E → D (1)

Đây là đồ thị có hướng. Trọng số cạnh D → E là -1 giúp minh họa khả năng xử lý trọng số âm của Bellman–Ford.

Demo Bellman–Ford bằng JavaScript

Demo dưới đây cho phép:

• Chọn đỉnh bắt đầu và đỉnh kết thúc.
• Chạy thuật toán Bellman–Ford với từng vòng lặp relax cạnh.
• Xem bảng khoảng cách sau từng bước.
• Xem log chi tiết các lần cập nhật và đường đi ngắn nhất cuối cùng.

Phân tích đoạn code Bellman–Ford

1. Khởi tạo khoảng cách và đỉnh trước

nodes.forEach(function(n) {
    distances[n] = Infinity;
    previous[n] = null;
});
distances[start] = 0;

Mọi đỉnh ban đầu đều có khoảng cách vô cùng (chưa biết đường đi), riêng đỉnh bắt đầu có khoảng cách 0. Mảng previous dùng để lưu đỉnh đứng trước trên đường đi ngắn nhất.

2. Lặp V - 1 lần và relax tất cả các cạnh

for (var i = 1; i <= V - 1; i++) {
    var updated = false;

    edges.forEach(function(edge) {
        var u = edge.from;
        var v = edge.to;
        var w = edge.w;

        if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
            distances[v] = distances[u] + w;
            previous[v] = u;
            updated = true;
        }
    });

    if (!updated) {
        break;
    }
}

Mỗi vòng lặp lan truyền thông tin khoảng cách thêm một cạnh. Nếu trong một vòng lặp không có cập nhật nào, thuật toán có thể dừng sớm vì mọi khoảng cách đã tối ưu.

3. Kiểm tra chu trình âm

var hasNegativeCycle = false;

edges.forEach(function(edge) {
    var u = edge.from;
    var v = edge.to;
    var w = edge.w;
    if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
        hasNegativeCycle = true;
    }
});

Sau V - 1 lần lặp, nếu vẫn có cạnh làm giảm khoảng cách, tức là tồn tại chu trình âm. Trong trường hợp đó, không thể xác định đường đi ngắn nhất vì có thể “quay” chu trình đó nhiều lần để làm tổng trọng số giảm vô hạn.

Khi nào nên dùng Bellman–Ford?

• Khi đồ thị có cạnh mang trọng số âm.
• Khi cần vừa tìm đường đi ngắn nhất, vừa kiểm tra chu trình âm.
• Khi số lượng cạnh và đỉnh không quá lớn (do độ phức tạp O(V × E)).
• Khi Dijkstra không thể sử dụng vì vi phạm điều kiện trọng số không âm.

Kết luận

Bellman–Ford là một thuật toán quan trọng trong nhóm thuật toán đường đi ngắn nhất. Dù chậm hơn Dijkstra trên đồ thị lớn, Bellman–Ford lại có lợi thế là xử lý được trọng số âm và phát hiện chu trình âm.

Với demo bằng JavaScript ở trên, bạn có thể quan sát trực tiếp cách thuật toán lặp nhiều vòng, relax các cạnh và dần dần hội tụ về khoảng cách ngắn nhất.

Khi đã hiểu rõ BFS, Dijkstra và Bellman–Ford, bạn đã nắm trong tay những công cụ nền tảng để giải quyết hầu hết các bài toán đường đi cơ bản trong lập trình và tối ưu hóa.