Bellman Ford

The Bellman-Ford algorithm is a way to compute the shortest path between a source node and all other nodes in the graph. Unlike Dijkstra's Algorithm, Bellman-Ford also works on graphs with negative edge weights, and it can be used to detect negative cycles in a graph. Bellman-Ford is also much shorter and easier to code than Dijkstra's algorithm.

The key idea is that a shortest path will not contain more than $V-1$ edges if there is no negative cycle—otherwise we'll be visiting nodes more than once, which can't be optimal. The algorithm then puts edges into place by iterating through the set of edges for each of the V nodes, and with each of these the algorithm checks if using the current edge makes the distance less. If so, the distance is decreased. This also means that the complexity is $O(EV)$.

The following is an implementation of Bellman-Ford in C++. The input is in the form
V E
v1 v2 w

where V is the number of vertices, E is the number of edges, and each v1 v2 w indicate the weight of the edge between two vertices.

This is a basic implementation with an edge list.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXV 100000
#define INFTY 10000000
using namespace std;
 
ifstream fin ("bellman.in");
ofstream fout ("bellman.out");
 
vector< vector<int> > el;
vector<int> tmp(3);
int v, e, bestd[MAXN];
 
main () {
    fin >> v >> e;
    for (int i = 0; i < e; i++) {
        fin >> tmp[0] >> tmp[1] >> tmp[2];
        el.push_back(tmp);
    }
    for (int i = 0; i < MAXV; i++) 
        bestd[i] = INFTY;
    bestd[0] = 0;
    // Bellman-Ford Algorithm
    for (int i = 1; i < v; i++)
        for (int j = 0; j < el.size(); j++)
            bestd[el[j][1]] = min(bestd[el[j][0]] + el[j][2], bestd[el[j][1]]);
    // Negative-cycle detection
    for (int i = 0; i < e; i++)
        if (bestd[el[i][1]] > bestd[el[i][0]] + el[i][2]) {
            cout << "Oh no, a negative cycle!" << endl;
            fout << "NONE" << endl;
            break;
        }
    // bestd[i] now contains the shortest distance from node 0 to i.
    for (int i = 0; i < v; i++)
        fout << i << " " << bestd[i] << endl;
    exit(0);
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License