Thuật toán Bellman-Ford trong C++

Bellman-Ford – Thuật toán quy hoạch động tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả đỉnh khác trong đồ thị có trọng số (có thể âm).

• Đề xuất bởi Alfonso Shimbel (1955), cải tiến bởi Richard Bellman & Lester Ford (1956, 1958).
• Chậm hơn Dijkstra (O(VE)) nhưng xử lý được trọng số âm.
• Phát hiện chu trình âm (negative cycle).

Thuật toán

Input: Đồ thị có trọng số, đỉnh nguồn s
Output: Khoảng cách ngắn nhất từ s đến mọi đỉnh; phát hiện chu trình âm

1. Khởi tạo dist[v] = ∞, dist[s] = 0
2. Lặp V-1 lần: với mỗi cạnh (u,v,w), nếu dist[u]+w < dist[v] thì cập nhật
3. Kiểm tra chu trình âm: nếu vẫn cập nhật được ở lần V thì có chu trình âm

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

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

void bellmanFord(int V, vector<Edge> edges, int src) {
    const int INF = 1e9;
    vector<int> dist(V, INF);
    dist[src] = 0;
    
    // Relax V-1 lần
    for (int i = 1; i <= V-1; i++) {
        for (auto &e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    
    // Kiểm tra chu trình âm
    bool hasNegCycle = false;
    for (auto &e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            hasNegCycle = true;
            break;
        }
    }
    
    if (hasNegCycle) {
        cout << "Do thi co chu trinh am!\n";
        return;
    }
    
    cout << "Dinh\tKhoang cach tu nguon\n";
    for (int i = 0; i < V; i++) {
        cout << i << "\t" << (dist[i]==INF?"INF":to_string(dist[i])) << "\n";
    }
}

int main() {
    int V = 5;
    vector<Edge> 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}
    };
    bellmanFord(V, edges, 0);
    return 0;
}

Kết quả

Dinh    Khoang cach tu nguon
0       0
1       -1
2       2
3       -2
4       1