Bellman-Ford Algorithm

Concept

As we learned in the previous section, Dijkstra’s Algorithm is the fastest way to find the shortest path, but it completely breaks and returns the wrong answer if the graph contains Negative Weights.

The Bellman-Ford Algorithm is the slower, but bulletproof alternative. It handles negative weights perfectly, and even has a built-in alarm system to detect Negative Weight Cycles (a loop of negative weights that allows you to loop infinitely to reach negative infinity cost!).

The Mechanism (Brute Force Relaxation)

Dijkstra is elegant. It uses a Priority Queue to carefully follow the fastest paths.
Bellman-Ford is brute force. It doesn’t use a Priority Queue. It doesn’t even use an Adjacency List! It operates directly on the raw edges array.

1. It initializes a distances array to Infinity.
2. It loops over the entire edges array, trying to relax (overwrite with a smaller number) every single edge in the graph.
3. Because the shortest path in a graph with V vertices can mathematically never exceed V - 1 edges, it runs the entire edge loop exactly V - 1 times.
4. By blindly brute-forcing every edge over and over, the shortest paths mathematically “propagate” through the entire network, perfectly resolving any negative weights.

Implementation

// Time Complexity: O(V * E) (Slower than Dijkstra's O(E log V))
// Space Complexity: O(V)

function bellmanFord(n: number, edges: number[][], startNode: number): number[] {
    const distances = new Array(n).fill(Infinity);
    distances[startNode] = 0;

    // Run the relaxation process exactly (Vertices - 1) times
    for (let i = 0; i < n - 1; i++) {
        // Iterate over EVERY SINGLE EDGE in the entire graph
        for (let [u, v, weight] of edges) {
            
            // If the source node has actually been reached...
            if (distances[u] !== Infinity) {
                // Calculate the new cost
                const newCost = distances[u] + weight;
                
                // RELAXATION: Overwrite if faster!
                if (newCost < distances[v]) {
                    distances[v] = newCost;
                }
            }
        }
    }

    // --- PHASE 2: Negative Cycle Detection ---
    // Mathematically, after V-1 iterations, the shortest paths MUST be locked.
    // If we run the loop ONE MORE TIME, and an edge STILL relaxes, 
    // it mathematically proves there is an infinite negative cycle!
    
    for (let [u, v, weight] of edges) {
        if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
            console.error("FATAL ERROR: Graph contains a negative weight cycle!");
            return []; // Shortest path is impossible (it's negative infinity)
        }
    }

    return distances;
}

The “Cheapest Flights Within K Stops” Problem

LeetCode #787. This is the absolute most famous problem that requires Bellman-Ford.
Problem: Find the cheapest price from src to dst with up to k stops.

Why can’t we use Dijkstra? Because Dijkstra optimizes purely for price! It might find a $5 flight, but that flight requires 100 stops, violating the k constraint.

Bellman-Ford is the perfect solution here because of its V - 1 iteration loop.
The outer loop in Bellman-Ford mathematically represents the “number of edges taken”.
If we simply cap the outer loop to run exactly k + 1 times (instead of V - 1 times), the algorithm will perfectly calculate the absolute cheapest flights taking at most k + 1 edges (which is exactly k stops)!

(Note: To solve Cheapest Flights, you must use a temporary clone of the distances array during each loop iteration to prevent a single edge from chaining forward multiple times in a single step).

Interview Questions

Q: Dijkstra takes $O(E \log V)$ time. Bellman-Ford takes $O(V \times E)$ time. Which is faster on a fully connected, dense graph?
A: In a highly dense graph where every node connects to every node, the number of edges $E$ is roughly $V^2$.
Dijkstra: $V^2 \log V$.
Bellman-Ford: $V \times V^2 = V^3$.
Dijkstra is significantly faster on almost all graphs, which is why Bellman-Ford is only used as a last resort when negative weights are explicitly involved, or when the problem explicitly constraints the maximum number of edges/stops.