Intro To Graph Algorithms - Learning Module

Loading content...

0/279

Shortest Paths — Dijkstra and Bellman-Ford

Finding the Best Route Through Weighted Networks

In the real world, not all connections are equal. Roads have different lengths, flights have different costs, and network links have different latencies. When we add weights to edges, the simple elegance of BFS's shortest-path guarantee breaks down—we need more sophisticated algorithms.

This page introduces two cornerstone algorithms for finding shortest paths in weighted graphs:

Dijkstra's Algorithm: The workhorse for non-negative weighted graphs, used in GPS systems, network routing, and countless applications.
Bellman-Ford Algorithm: The reliable alternative when negative weights exist, capable of detecting negative cycles.

Understanding these algorithms—their mechanics, guarantees, and limitations—is essential for solving optimization problems in weighted networks.

What You Will Learn

By the end of this page, you will understand why BFS fails with weighted edges, how Dijkstra's greedy approach works and why it requires non-negative weights, how Bellman-Ford uses repeated relaxation to handle negative weights, when to use each algorithm, and their time/space complexity trade-offs.

Why BFS Fails for Weighted Graphs

Before diving into solutions, let's understand the problem. BFS guarantees shortest paths in unweighted graphs because it explores vertices in order of edge count. But with weights, edge count doesn't equal path cost.

Consider this example:

    A -----(1)-----> B
    |                |
  (10)              (1)
    |                |
    v                v
    C -----(1)-----> D

Shortest path from A to D:

Path A → C → D: cost = 10 + 1 = 11
Path A → B → D: cost = 1 + 1 = 2 ✓ (shortest)

What BFS would do: BFS explores level-by-level. From A, it discovers B and C (both at distance 1 edge). If C is processed before B's path to D is complete, BFS might "finalize" C's neighbors before realizing the B → D path is cheaper.

BFS's invariant—"first discovery is shortest path"—only holds when all edges have equal weight.

The Core Problem

BFS processes vertices in discovery order, but discovery order doesn't correspond to cost order in weighted graphs. A vertex discovered later via more edges might have lower total cost than a vertex discovered earlier via fewer edges. We need to process vertices in cost order, not discovery order.

The Solution Insight:

Instead of processing vertices in FIFO order (queue), we need to process them in minimum distance order. This is exactly what Dijkstra's algorithm does—using a priority queue to always select the unprocessed vertex with the smallest known distance.

This transforms BFS's level-by-level exploration into a cost-by-cost exploration.

Dijkstra's Algorithm: The Greedy Shortest Path Finder

Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959, remains one of the most important and widely-used graph algorithms. It finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.

The Core Idea: Greedy Selection + Relaxation

Maintain tentative distances: Initially, distance to source is 0; all others are infinity.
Greedy selection: Always process the unvisited vertex with the smallest tentative distance.
Relaxation: When processing a vertex, update (relax) distances to its neighbors if a shorter path is found.
Finalization: Once a vertex is processed, its distance is final (the greedy choice guarantees this).

The Dijkstra Invariant:

When a vertex is extracted from the priority queue, its distance is the true shortest distance from the source.

This invariant is the mathematical heart of Dijkstra's correctness—and it only holds for non-negative weights.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
interface WeightedEdge {
    to: number;
    weight: number;
}
 
interface WeightedGraph {
    neighbors(vertex: number): WeightedEdge[];
    numVertices: number;
}
 
class MinHeap<T> {
    private heap: { priority: number; value: T }[] = [];
    
    push(priority: number, value: T): void {
        this.heap.push({ priority, value });
        this.bubbleUp(this.heap.length - 1);
    }
    
    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const result = this.heap[0].value;
        const last = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return result;
    }
    
    isEmpty(): boolean { return this.heap.length === 0; }
    
    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent].priority <= this.heap[idx].priority) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    
    private bubbleDown(idx: number): void {
        const n = this.heap.length;
        while (true) {
            const left = 2 * idx + 1, right = 2 * idx + 2;
            let smallest = idx;
            if (left < n && this.heap[left].priority < this.heap[smallest].priority) smallest = left;
            if (right < n && this.heap[right].priority < this.heap[smallest].priority) smallest = right;
            if (smallest === idx) break;
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}
 
function dijkstra(graph: WeightedGraph, source: number): { 
    distances: number[], 
    predecessors: (number | null)[] 
} {
    const n = graph.numVertices;
    const distances = new Array(n).fill(Infinity);
    const predecessors: (number | null)[] = new Array(n).fill(null);
    const visited = new Array(n).fill(false);
    
    const pq = new MinHeap<number>();
    distances[source] = 0;
    pq.push(0, source);
    
    while (!pq.isEmpty()) {
        const current = pq.pop()!;
        
        // Skip if already processed (stale entry)
        if (visited[current]) continue;
        visited[current] = true;
        
        // Relax all outgoing edges
        for (const { to, weight } of graph.neighbors(current)) {
            const newDist = distances[current] + weight;
            
            if (newDist < distances[to]) {
                distances[to] = newDist;
                predecessors[to] = current;
                pq.push(newDist, to);
            }
        }
    }
    
    return { distances, predecessors };
}
 
// Reconstruct shortest path from source to target
function reconstructPath(predecessors: (number | null)[], target: number): number[] {
    const path: number[] = [];
    let current: number | null = target;
    
    while (current !== null) {
        path.push(current);
        current = predecessors[current];
    }
    
    return path.reverse();
}

Step-by-Step Execution:

Consider this graph (source = A):

    A ---(4)---> B
    |           /|
   (2)       (1) |
    |       /   (5)
    v     v      |
    C ---(3)---> D

Step	PQ State	Process	Distances After	Notes
0	[(0,A)]	—	A:0, B:∞, C:∞, D:∞	Initialize
1	[]	A	A:0, B:4, C:2, D:∞	Relax B, C from A
2	[(2,C), (4,B)]	C	A:0, B:4, C:2, D:5	Relax D from C
3	[(4,B), (5,D)]	B	A:0, B:4, C:2, D:5	B→D would be 4+5=9, no improvement
4	[(5,D)]	D	A:0, B:4, C:2, D:5	D has no outgoing edges
Done	[]	—	Final: A:0, B:4, C:2, D:5

Shortest path A→D: A → C → D with cost 5.

Why Dijkstra Requires Non-Negative Weights

Dijkstra's algorithm is greedy: once a vertex is processed, its distance is considered final. This works because, with non-negative weights, we can't find a shorter path by going through a vertex with higher current distance.

The Formal Argument:

Suppose vertex u is extracted from the priority queue with distance d[u]. For any unprocessed vertex v with d[v] > d[u], any path to u through v would have cost ≥ d[v] > d[u]. Since all edge weights are non-negative, adding more edges can't reduce this. Therefore, d[u] is optimal.

What Breaks with Negative Weights:

With negative weights, a longer path (more edges, higher intermediate distances) might end up shorter due to negative edges later.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Graph:
    A ---(1)---> B
    |            |
   (5)        (-10)
    |            |
    v            v
    C            D
 
Dijkstra from A:
Step 1: Process A (dist 0), relax B→1, C→5
        PQ: [(1,B), (5,C)]
        
Step 2: Process B (dist 1) ← FINALIZED!
        Relax D → 1 + (-10) = -9
        PQ: [(-9,D), (5,C)]
        
Step 3: Process D (dist -9), no outgoing edges
        PQ: [(5,C)]
        
Step 4: Process C (dist 5), no improvements
        PQ: []
 
RESULT: dist[B] = 1
 
BUT WAIT! Path A → C → B would cost... 
Oh, but C→B doesn't exist. Let's modify:
 
    A ---(1)---> B
    |            ^
   (5)        (-10)
    |            |
    v            |
    C -----------+
 
Now:
- Dijkstra still finalizes B at distance 1
- But path A → C → B = 5 + (-10) = -5 < 1 !
 
Dijkstra returned the WRONG answer because it finalized B 
before discovering the cheaper path through C.

Critical Limitation

Never use Dijkstra's algorithm on graphs with negative edge weights. The algorithm's greedy assumption breaks, and it can return incorrect shortest paths. Use Bellman-Ford instead for graphs with negative weights.

Bellman-Ford Algorithm: Handling Negative Weights

The Bellman-Ford algorithm takes a different approach. Instead of greedily finalizing vertices, it systematically relaxes all edges, repeating this process V-1 times. This guarantees that the shortest path information "propagates" through the graph, even with negative weights.

The Core Idea: Repeated Relaxation

Initialize distances: source = 0, all others = infinity
Repeat V-1 times: For each edge (u, v, w), relax it: if d[u] + w < d[v], then d[v] = d[u] + w
(Optional) Check for negative cycles: If any edge can still be relaxed, a negative cycle exists

Why V-1 Iterations?

The shortest path between any two vertices contains at most V-1 edges (in a graph with V vertices). Each iteration propagates the shortest path information one edge further. After V-1 iterations, all shortest paths have been computed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
interface Edge {
    from: number;
    to: number;
    weight: number;
}
 
interface BellmanFordResult {
    distances: number[];
    predecessors: (number | null)[];
    hasNegativeCycle: boolean;
}
 
function bellmanFord(
    numVertices: number, 
    edges: Edge[], 
    source: number
): BellmanFordResult {
    // Initialize distances
    const distances = new Array(numVertices).fill(Infinity);
    const predecessors: (number | null)[] = new Array(numVertices).fill(null);
    distances[source] = 0;
    
    // Relax all edges V-1 times
    for (let i = 0; i < numVertices - 1; i++) {
        let anyRelaxed = false;
        
        for (const { from, to, weight } of edges) {
            if (distances[from] !== Infinity) {
                const newDist = distances[from] + weight;
                
                if (newDist < distances[to]) {
                    distances[to] = newDist;
                    predecessors[to] = from;
                    anyRelaxed = true;
                }
            }
        }
        
        // Early termination: if no relaxation happened, we're done
        if (!anyRelaxed) break;
    }
    
    // Check for negative cycles (V-th iteration)
    let hasNegativeCycle = false;
    for (const { from, to, weight } of edges) {
        if (distances[from] !== Infinity && 
            distances[from] + weight < distances[to]) {
            hasNegativeCycle = true;
            break;
        }
    }
    
    return { distances, predecessors, hasNegativeCycle };
}
 
// Example: Detecting arbitrage opportunities
// Currencies as vertices, exchange rates as edges
// Negative cycle = arbitrage opportunity!
function detectArbitrage(rates: number[][], currencies: string[]): boolean {
    const n = currencies.length;
    const edges: Edge[] = [];
    
    // Convert multiplicative rates to additive (log)
    // If going A→B→C→A gives rate > 1, we have arbitrage
    // log(rate) > 0 means profit, so we want negative cycle in -log(rate)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j && rates[i][j] > 0) {
                edges.push({ 
                    from: i, 
                    to: j, 
                    weight: -Math.log(rates[i][j])  // Negative log
                });
            }
        }
    }
    
    const result = bellmanFord(n, edges, 0);
    return result.hasNegativeCycle;
}

Understanding Bellman-Ford Through an Example:

Graph with negative edge:

    A ---(4)---> B
    |            |
   (3)         (-6)
    |            |
    v            v
    C ---(2)---> D

Edges: (A,B,4), (A,C,3), (B,D,-6), (C,D,2)

Iteration	B	C	D	Notes
Init	∞	∞	∞	Source = A
1	4	3	5	Relax A→B, A→C, C→D
2	4	3	-2	Relax B→D: 4+(-6)=-2 < 5
3	4	3	-2	No changes

Shortest path A→D = -2 via A → B → D (not A → C → D = 5).

The negative edge B→D created a shorter path that Bellman-Ford correctly found.

Negative Cycle Detection

If after V-1 iterations, any edge can still be relaxed, a negative cycle exists. Why? A shortest path has at most V-1 edges. If we can still improve after V-1 iterations, we must be finding "better" paths with more edges—which means some cycle is reducing the total cost. That cycle must have negative weight.

Dijkstra vs Bellman-Ford: When to Use Which

Both algorithms solve the single-source shortest path problem, but they have different strengths and use cases:

Dijkstra vs Bellman-Ford Comparison
Aspect	Dijkstra	Bellman-Ford
Time Complexity	O((V + E) log V) with binary heap	O(V × E)
Space Complexity	O(V)	O(V)
Negative Weights	❌ Not supported	✅ Supported
Negative Cycles	❌ Cannot detect	✅ Can detect
Best for	GPS, network routing, most real-world cases	Currency arbitrage, systems with negative costs
Implementation	More complex (priority queue)	Simpler (nested loops)
Early Termination	When target is reached	When no relaxation occurs

Decision Matrix:

Does your graph have negative edge weights?
├── No  → Use Dijkstra (faster)
└── Yes → Could there be negative cycles?
    ├── No (you're sure)  → Bellman-Ford works
    └── Possibly           → Bellman-Ford (will detect them)

Real-World Context:

Dijkstra dominates in road networks (distances are positive), network routing (latencies are positive), and game pathfinding (costs are positive).
Bellman-Ford is essential for financial applications (currency exchange can create "negative cost" cycles = arbitrage), systems modeling where costs can be rewards (negative), and when you must detect negative cycles.

Hybrid Approach: Johnson's Algorithm

For all-pairs shortest paths with negative weights, Johnson's algorithm combines both: run Bellman-Ford once to reweight edges (eliminating negative weights), then run Dijkstra from each vertex. This achieves O(VE + V² log V) for all-pairs, better than Floyd-Warshall's O(V³) for sparse graphs.

Complexity Analysis Deep Dive

Dijkstra's Complexity:

The complexity depends on the priority queue implementation:

Priority Queue	Extract-Min	Decrease-Key	Total Dijkstra
Binary Heap	O(log V)	O(log V)	O((V + E) log V)
Fibonacci Heap	O(log V) amortized	O(1) amortized	O(E + V log V)
Array (no heap)	O(V)	O(1)	O(V² + E)

Analysis for Binary Heap (standard implementation):

Each vertex is extracted once: O(V log V)
Each edge is relaxed once, potentially causing an insert/decrease: O(E log V)
Total: O((V + E) log V)

For sparse graphs (E ≈ V): O(V log V) For dense graphs (E ≈ V²): O(V² log V)

Note on Decrease-Key:

True decrease-key operations require a more complex heap (Fibonacci heap) or index tracking. The common workaround is to push a new entry for each update and skip stale entries when extracting. This can increase heap size but maintains O((V + E) log V) complexity.

Bellman-Ford's Complexity:

The analysis is straightforward:

Outer loop: V - 1 iterations
Inner loop: E edge relaxations
Total: O(V × E)

Comparing on Different Graph Types:

Graph Type	V	E	Dijkstra	Bellman-Ford
Sparse (tree-like)	10,000	10,000	~130,000 ops	~100,000,000 ops
Dense (near-complete)	1,000	500,000	~5,000,000 ops	~500,000,000 ops
Road network	1,000,000	3,000,000	~60,000,000 ops	~3,000,000,000,000 ops

Dijkstra is overwhelmingly faster for typical graphs. Bellman-Ford's virtue is correctness with negative weights, not speed.

Practical Considerations

For very large graphs (millions of vertices), even Dijkstra may be slow. Practical systems use heuristics (A* search), preprocessing (contraction hierarchies used in GPS), or hierarchical decomposition. These advanced techniques build on Dijkstra's foundation.

Common Pitfalls and Edge Cases

Understanding the algorithms conceptually is one thing; implementing them correctly is another. Here are common pitfalls:

Pitfall 1: Using Dijkstra with Negative Weights

The most common error. Always verify your graph has non-negative weights before using Dijkstra.

Pitfall 2: Forgetting to Handle Unreachable Vertices

Vertices not reachable from the source will have distance = infinity. Handle this in path reconstruction and when reporting results.

Pitfall 3: Integer Overflow with Infinity

If using large integers for infinity (e.g., INT_MAX), adding a weight can overflow. Use Infinity in JavaScript/TypeScript, or check before adding.

// WRONG: Can overflow
if (dist[u] + weight < dist[v]) ...

// CORRECT: Check first
if (dist[u] !== Infinity && dist[u] + weight < dist[v]) ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Edge Case 1: Unreachable vertices
function dijkstraWithValidation(
    graph: WeightedGraph, 
    source: number, 
    target: number
): { distance: number; path: number[] } | null {
    const { distances, predecessors } = dijkstra(graph, source);
    
    // Target unreachable
    if (distances[target] === Infinity) {
        return null;
    }
    
    const path = reconstructPath(predecessors, target);
    return { distance: distances[target], path };
}
 
// Edge Case 2: Self-loops (edge from vertex to itself)
// These are automatically handled—a self-loop u→u with weight w
// would try to relax: dist[u] + w < dist[u]
// For positive w, this is false, so no issue.
// For negative w, this indicates a (trivial) negative cycle.
 
// Edge Case 3: Parallel edges (multiple edges between same vertices)
// Both algorithms handle this correctly. Each edge is relaxed,
// and the minimum-weight one will produce the shortest distance.
 
// Edge Case 4: Disconnected graph
function shortestPathInDisconnectedGraph(
    graph: WeightedGraph,
    source: number,
    target: number
): number {
    // First check if target is reachable
    const reachable = bfsReachability(graph, source);
    if (!reachable.has(target)) {
        return -1; // Convention: -1 for unreachable
    }
    
    const { distances } = dijkstra(graph, source);
    return distances[target];
}

Negative Cycle Behavior

If a negative cycle is reachable from the source, the concept of "shortest path" becomes undefined—you can keep going around the cycle to reduce cost infinitely. Bellman-Ford detects this. Dijkstra will simply give wrong answers. Always check for negative cycles in graphs that might have negative weights.

Summary: Shortest Paths in Weighted Graphs

Dijkstra's and Bellman-Ford are the two foundational algorithms for finding shortest paths in weighted graphs. Understanding their mechanisms, guarantees, and limitations is essential for solving optimization problems.

Key Takeaways

•BFS fails for weighted graphs because discovery order ≠ cost order.
•Dijkstra uses a priority queue to process vertices in minimum-distance order—O((V+E) log V).
•Dijkstra's greedy approach requires non-negative weights for correctness.
•Bellman-Ford relaxes all edges V-1 times—O(V × E), slower but handles negative weights.
•Bellman-Ford can detect negative cycles by checking for further relaxation after V-1 iterations.
•Choose Dijkstra for non-negative weights (most real-world cases).
•Choose Bellman-Ford when negative weights exist or negative cycle detection is needed.

What's Next:

With shortest paths covered, the next page explores Minimum Spanning Trees—algorithms for connecting all vertices at minimum total cost. You'll see how Prim's algorithm resembles Dijkstra (greedy vertex selection) and how Kruskal's algorithm takes a globally greedy approach with Union-Find.

Page Complete

You now understand the two fundamental shortest-path algorithms for weighted graphs. Dijkstra's efficiency makes it the workhorse for most applications, while Bellman-Ford's robustness handles the special case of negative weights. Next, we'll explore minimum spanning trees—optimal ways to connect an entire network.