Bellman Ford Algorithm

A dynamic algorithm to find the shortest paths from a source node to all other node in a weighted graph. Can handle graphs with negative weight edges. Fails for graphs with negative weight cycle.

Steps

1. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
2. Relax all edges $V - 1$ times. For each edge $(u, v)$ with weight $w$, if $\text{dist}(u) + w < \text{dist}(v)$, update the distance to $v$.
3. Check for negative weight cycles by iterating through all edges one more time. If a shorter path is found, it indicates the presence of a negative weight cycle.

Implementation

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>

using namespace std;

// Function to print the distances from the source vertex
void printDistances(vector<int>& dist) {
    cout << "Vertex\tDistance from Source\n";
    for (int i = 0; i < dist.size(); i++) {
        cout << i << "\t" << (dist[i] == INT_MAX ? "INF" : to_string(dist[i])) << "\n";
    }
}

// Bellman-Ford algorithm function
void bellmanFord(int V, int E, vector<tuple<int, int, int>>& edges, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    // Relax all edges |V| - 1 times
    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < E; j++) {
            int u, v, w;
            tie(u, v, w) = edges[j];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    for (int j = 0; j < E; j++) {
        int u, v, w;
        tie(u, v, w) = edges[j];
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "Graph contains a negative weight cycle\n";
            return;
        }
    }

    // Print the distances
    printDistances(dist);
}

int main() {
    int V = 5; // Number of vertices
    int E = 8; // Number of edges

    // Graph edges represented as (u, v, w) where u -> v with weight w
    vector<tuple<int, int, int>> 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}
    };

    int src = 0; // Source vertex
    bellmanFord(V, E, edges, src);

    return 0;
}

Example

Consider the following graph:

• Initialize: $d[0] = 0$, $d[1] = d[2] = d[3] = d[4] = \infty$, predecessors = null.
• Relax Edges (4 iterations):
  • Iteration 1:
    • 0→1: $0+2=2$, $d[1]=2$, $pred[1]=0$.
    • 0→2: $0+3=3$, $d[2]=3$, $pred[2]=0$.
    • 0→4: $0+1=1$, $d[4]=1$, $pred[4]=0$.
    • 4→3: $1+2=3$, $d[3]=3$, $pred[3]=4$.
  • Iterations 2-4: No further updates.
• Check Negative Cycles: No distances decrease, so no negative cycles.

Final Results:

• Distances: $d[0]=0$, $d[1]=2$, $d[2]=3$, $d[3]=3$, $d[4]=1$.
• Paths:
  • 0→1: $0\to1$ (2)
  • 0→2: $0\to2$ (3)
  • 0→3: $0\to4\to3$ (1+2=3)
  • 0→4: $0\to4$ (1)

Bellman-Ford works by relaxing all edges $|V|-1$ times, handling negative weights if present (none here). $$

Comparison from Dijkstra’s algorithm