Bellman-Ford Algorithm for Shortest Path

Given a weighted directed graph and a source vertex, find the shortest paths from the source to all other vertices in the graph. Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can handle graphs containing negative weight edges.

Why Bellman-Ford?

While Dijkstra's Algorithm is faster with a time complexity of $O(E \log V)$, it is a greedy algorithm and fails when the graph contains edges with negative weights.

Bellman-Ford uses a Dynamic Programming approach. It relaxes all edges $V - 1$ times to guarantee the correct shortest path, and can also detect the presence of negative weight cycles (cycles whose sum of edge weights is negative).

⚠️

If a graph contains a negative weight cycle, a shortest path cannot be defined because you can traverse the cycle infinitely to make the path weight infinitely negative. Bellman-Ford detects this and reports it.

How It Works (Step-by-Step)

A shortest path in a graph with $V$ vertices can contain at most $V - 1$ edges. Therefore, if we relax all edges $V - 1$ times, we are guaranteed to find the shortest path.

Initialize Distances: Create an array dist of size $V$. Set all distances to Infinity except the source vertex: dist[src] = 0.
Relax Edges ($V-1$ times): For each edge $u \rightarrow v$ with weight $w$:
- If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
Detect Negative Cycles: Loop through all edges one more time. For each edge $u \rightarrow v$ with weight $w$:
- If dist[u] + w < dist[v], then the graph contains a negative weight cycle.

Visual Example Walkthrough

Let's find the shortest path from source A in this directed graph:

Trace Table (Source = A)

Iteration	A	B	C	D	E
Initial	`0`	`Infinity`	`Infinity`	`Infinity`	`Infinity`
Iteration 1	`0`	`-1`	`2`	`-2`	`1`
Iteration 2	`0`	`-1`	`2`	`-2`	`1`

(Subsequent iterations 3 and 4 do not change the distances since the shortest paths are already finalized.)

Final Shortest Distances:

A = 0
B = -1
C = 2
D = -2
E = 1

JavaScript Code Implementation

class Edge {
    constructor(src, dest, weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}
 
class Graph {
    constructor(verticesCount) {
        this.vertices = verticesCount;
        this.edges = [];
        this.vertexMap = {}; // Maps node letters to index numbers
        this.revVertexMap = {};
        this.vertexCounter = 0;
    }
 
    // Helper to get or assign vertex index
    _getVertexIndex(v) {
        if (this.vertexMap[v] === undefined) {
            this.vertexMap[v] = this.vertexCounter;
            this.revVertexMap[this.vertexCounter] = v;
            this.vertexCounter++;
        }
        return this.vertexMap[v];
    }
 
    addEdge(src, dest, weight) {
        const u = this._getVertexIndex(src);
        const v = this._getVertexIndex(dest);
        this.edges.push(new Edge(u, v, weight));
    }
 
    // Bellman-Ford Algorithm
    bellmanFord(srcSymbol) {
        const src = this.vertexMap[srcSymbol];
        const dist = new Array(this.vertices).fill(Infinity);
        dist[src] = 0;
 
        // Step 1: Relax all edges V - 1 times
        for (let i = 1; i < this.vertices; i++) {
            for (let edge of this.edges) {
                const u = edge.src;
                const v = edge.dest;
                const weight = edge.weight;
 
                if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
 
        // Step 2: Check for negative-weight cycles
        for (let edge of this.edges) {
            const u = edge.src;
            const v = edge.dest;
            const weight = edge.weight;
 
            if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
                console.log("Graph contains a negative weight cycle!");
                return null;
            }
        }
 
        this._printSolution(dist);
        return dist;
    }
 
    _printSolution(dist) {
        console.log("Vertex \t Distance from Source");
        for (let i = 0; i < this.vertices; i++) {
            console.log(`${this.revVertexMap[i]} \t\t ${dist[i]}`);
        }
    }
}
 
// Driver code matching the example
const g = new Graph(5);
g.addEdge("A", "B", -1);
g.addEdge("A", "C", 4);
g.addEdge("B", "C", 3);
g.addEdge("B", "D", 2);
g.addEdge("B", "E", 2);
g.addEdge("D", "B", 1);
g.addEdge("D", "C", 5);
g.addEdge("E", "D", -3);
 
g.bellmanFord("A");
/*
Output:
Vertex   Distance from Source
A                0
B                -1
C                2
D                -2
E                1
*/

Complexity Analysis

Time Complexity: $O(V \cdot E)$
- Outer loop runs $V - 1$ times.
- Inner loop relaxes all $E$ edges in every iteration.
Space Complexity: $O(V)$
- To store distances array dist.

Dijkstra's Shortest Path Introduction to Trie