G-41: Bellman Ford Algorithm

The Bellman-Ford algorithm is a single-source shortest path algorithm capable of finding the shortest path from a starting node to all other nodes in a graph, even when Negative Edge Weights are present. Unlike Dijkstra's algorithm—which fails or falls into Time Limit Exceeded (TLE) loops when encountering negative weights or negative cycles—Bellman-Ford correctly computes shortest paths and explicitly detects negative cycles.

1. Why Do We Need Bellman-Ford? (Limitations of Dijkstra)

While Dijkstra's algorithm is efficient ($O(E \log V)$), it relies on a greedy assumption: once a node is popped from the priority queue, its shortest distance is finalized. This assumption breaks down under certain conditions:

2. Core Mental Model: The Chain Reaction Analogy

To understand how shortest paths propagate through a graph, imagine a row of dominoes or a relay race where information travels sequentially.

• The Source Node ($0$) starts with a distance of $0$.
• In Iteration 1, node $0$ can update its direct neighbors (e.g., node $1$).
• In Iteration 2, node $1$ (having now been reached and updated) can pass its accumulated distance to its neighbors (e.g., node $2$ or node $5$).
• Each complete pass across all edges allows shortest-path information to propagate one hop further across the graph.

3. Handling Undirected vs. Directed Graphs

The Bellman-Ford algorithm is designed strictly for Directed Graphs (DG).

Converting Undirected Graphs to Directed Graphs

If you are given an undirected edge between node 1 and node 2 with weight 5:

• You cannot apply Bellman-Ford directly.
• Solution: Break the undirected edge into two directed edges: one going from 1 -> 2 (weight 5) and one going from 2 -> 1 (weight 5).

4. The Core Operation: Edge Relaxation

The foundational rule of Bellman-Ford is Edge Relaxation.

Relaxation Definition

For any directed edge from node $U$ to node $V$ with edge weight $wt$:

If: distance[U] + wt < distance[V]
Then: distance[V] = distance[U] + wt

In plain English: If the distance to reach node $U$ plus the cost of traveling from $U$ to $V$ is strictly less than our current best known distance to reach $V$, we have found a shorter path. Update $V$'s distance.

5. Why Exactly $V - 1$ Iterations?

In a graph with $V$ vertices, the longest possible shortest path without repeating any vertex (i.e., a simple path) can contain at most $V - 1$ edges.

• In the worst-case linear chain (where node at the bottom depends on node above it, which depends on the one above it, down to the source), each iteration of relaxing all edges guarantees that the shortest path information flows down by at least one hop.
• Therefore, after $V - 1$ complete iterations over all edges, all shortest paths across any valid graph structure are guaranteed to be fully computed.

6. Detecting Negative Cycles

A negative cycle is a closed loop in a graph where the sum of edge weights is less than $0$.

The Detection Rule

1. Run the standard Bellman-Ford relaxation process for $V - 1$ iterations.
2. Perform one extra ($V^{\text{th}}$) iteration over all edges.
3. If any edge can still be relaxed (i.e., distance[U] + wt < distance[V] is still true), it proves that a negative cycle exists, because shortest paths should stop shrinking after $V-1$ iterations unless trapped in a negative weight loop.

7. Step-by-Step Algorithm Walkthrough

1. Initialize Distance Array: Set distance[source] = 0 and all other nodes to 1e8 (Infinity).
2. Edge List Format: Store all directed edges as tuples: (u, v, weight). Edges can be provided in any arbitrary, jumbled order.
3. Main Loop ($V - 1$ times):
   • Loop through every edge (u, v, wt) in the edge list.
   • Apply the relaxation check.
4. Negative Cycle Check ($V^{\text{th}}$ iteration):
   • Loop through all edges one more time.
   • If any distance updates, return an error state (or array of -1).

8. Complete Implementation (C++ & Java Equivalents)

Below is the complete production-ready implementation of the Bellman-Ford algorithm, handling source distances, edge relaxations, and negative cycle detection.

C++ Implementation

class Solution {
public:
    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
        vector<int> dist(V, 1e8);
        dist[S] = 0;
        
        // Step 1: Relax all edges V - 1 times
        for (int i = 0; i < V - 1; i++) {
            for (auto it : edges) {
                int u = it[0];
                int v = it[1];
                int wt = it[2];
                
                if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {
                    dist[v] = dist[u] + wt;
                }
            }
        }
        
        // Step 2: Nth relaxation to check for negative cycle
        for (auto it : edges) {
            int u = it[0];
            int v = it[1];
            int wt = it[2];
            
            if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {
                // Negative cycle detected! Return {-1}
                return {-1};
            }
        }
        
        return dist;
    }
};

9. Complexity Analysis

• Time Complexity: $\mathcal{O}(V \times E)$
  • We iterate $V - 1$ times, and in each iteration, we traverse all $E$ edges. In the worst-case dense graph where $E \approx V^2$, the time complexity approaches $\mathcal{O}(V^3)$.
• Space Complexity: $\mathcal{O}(V)$
  • Required for maintaining the distance array of size $V$ (plus storage for the edge list).

Summary and Key Takeaways

• Shortest Path with Negative Edges: Bellman-Ford successfully computes single-source shortest paths even when negative edge weights exist.
• Negative Cycle Detection: Unlike Dijkstra, Bellman-Ford identifies negative cycles via a $V^{\text{th}}$ edge relaxation check.
• Directed Graph Requirement: The algorithm operates strictly on directed graphs; undirected graphs must be converted by splitting every edge into two directed edges.
• Sequential Edge Relaxation: All edges must be relaxed sequentially across $V - 1$ iterations to allow propagation across the longest possible simple path.
• Why $V - 1$ Iterations?: In the worst-case chain graph, information takes $V - 1$ hops to travel from the top node to the bottom node.
• Time Complexity: $\mathcal{O}(V \times E)$, making it slower than Dijkstra's algorithm ($\mathcal{O}(E \log V)$), but necessary when negative weights are present.
• Error Return: If a negative cycle is detected during the extra relaxation pass, the standard convention is to return an array containing -1.