Single-Source Shortest Paths in Directed Graphs

Motivation: Why BFS Breaks Down in Weighted Directed Graphs

  • BFS works perfectly for shortest paths in unweighted graphs because it explores the network layer by layer, always guaranteeing the shortest path in terms of the number of edges.
  • But BFS fails on weighted graphs:
    • Real-world networks (e.g., road maps, computer routing) use edge weights (distance, time, cost).
    • BFS assumes fewer edges = shorter path, but in weighted graphs, a path with more edges could actually have a lower total cost than a short path containing a heavy edge.
    • Key issue: Once BFS visits a node, it immediately marks it as “visited” and will never reconsider or update it. If a better (lower-cost) path is discovered later via a longer route, BFS ignores it—it cannot backtrack or update already-visited nodes.
  • Conclusion: In weighted graphs, we need to shift from counting the number of edges to tracking total path cost to find true shortest paths.

1. Dijkstra’s Algorithm

Intuition

  • Dijkstra’s algorithm is a greedy algorithm for finding shortest paths in weighted graphs.
  • Maintains a frontier of reached nodes, always selecting the node with the smallest tentative distance to “lock in” next.
  • Assumes all edge weights are positive, so taking longer detours can only increase the total cost.
  • As a result, the current shortest-known path to the closest frontier node is guaranteed to be the true shortest path.

The Catch: Negative Edge Weights

  • Dijkstra’s algorithm fails with negative edge weights due to its greedy strategy:
    • If a negative edge exists further down a path, a detour that once seemed expensive could become the best route.
    • Once Dijkstra “locks in” a node, it never revisits or updates its shortest path even if a better one is later found via a negative edge.
    • This can lead to incorrect shortest path results in graphs containing negative edges.

Pseudocode

Plaintext

Dijkstra(Graph, source):
    Initialize distance array dist[] to infinity for all nodes
    Initialize visited set S to empty
    dist[source] = 0
    Insert all nodes into a Priority Queue Q, keyed by dist[]

    while Q is not empty:
        u = Q.extract_min()      // Grab closest unvisited node
        Add u to S               // Permanently lock node u

        for each neighbor v of u:
            if v is not in S:
                new_dist = dist[u] + weight(u, v)
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    Q.decrease_key(v, new_dist) // Update priority
                    
    return dist

Toy Example

Consider a 3-node graph with a source node \(A\):

  • Edges: \(A \xrightarrow{5} B\), \(A \xrightarrow{2} C\), \(C \xrightarrow{1} B\)

Plaintext

Initialization:
  dist = {A: 0, B: ∞, C: ∞}
  Priority Queue Q = [(A, 0), (B, ∞), (C, ∞)]

Step 1: Extract min node 'A' (dist=0).
  Relax neighbors of A:
    - Neighbor B: new_dist = 0 + 5 = 5. update dist[B] = 5
    - Neighbor C: new_dist = 0 + 2 = 2. update dist[C] = 2
  Q is now: [(C, 2), (B, 5)]

Step 2: Extract min node 'C' (dist=2). 
  Node C is now locked. Relax neighbors of C:
    - Neighbor B: new_dist = dist[C] + weight(C,B) = 2 + 1 = 3.
    - Since 3 < 5, update dist[B] = 3.
  Q is now: [(B, 3)]

Step 3: Extract min node 'B' (dist=3). Node B is locked.

Final Shortest Paths from A: {A: 0, B: 3, C: 2}

2. The Bellman–Ford Algorithm

Intuition

  • Bellman–Ford is not greedy; it uses a dynamic programming method called relaxation.
  • Key fact: in a graph with \(V\) vertices, the longest possible simple shortest path has at most \(V-1\) edges (no cycles).
  • The algorithm:
    • Sequentially relaxes every edge in the graph.
    • Repeats this process \(V-1\) times to guarantee shortest paths propagate fully, regardless of edge weights.
  • Handles negative edge weights naturally.
  • Can detect negative cycles (paths whose total weight is negative):
    • After \(V-1\) passes, runs one extra (\(V\)-th) pass over all edges.
    • If any shortest path estimate decreases in this extra pass, a negative cycle exists.

Pseudocode

Plaintext

BellmanFord(Graph, source):
    Initialize distance array dist[] to infinity for all nodes
    dist[source] = 0

    // Loop V-1 times
    for i from 1 to |V| - 1:
        for each edge (u, v) in Graph:
            if dist[u] + weight(u, v) < dist[v]:
                dist[v] = dist[u] + weight(u, v)

    // V-th pass to check for negative cycles
    for each edge (u, v) in Graph:
        if dist[u] + weight(u, v) < dist[v]:
            throw Error("Graph contains a negative weight cycle")

    return dist

Toy Example (With a Negative Edge)

Consider a graph with source \(A\):

  • Vertices \(V = \{A, B, C\}\) (Requires \(|V|-1 = 2\) passes)
  • Edges: \(A \xrightarrow{4} B\), \(A \xrightarrow{3} C\), \(B \xrightarrow{-2} C\)

Plaintext

Initialization:
  dist = {A: 0, B: ∞, C: ∞}

Pass 1: Relax all edges (Order of edge processing can be random)
  - Inspect (A, B): dist[A] + 4 = 4  < dist[B] (∞)  -> dist[B] = 4
  - Inspect (A, C): dist[A] + 3 = 3  < dist[C] (∞)  -> dist[C] = 3
  - Inspect (B, C): dist[B] + (-2) = 4 - 2 = 2 < dist[C] (3) -> dist[C] = 2
  End of Pass 1: dist = {A: 0, B: 4, C: 2}

Pass 2: Relax all edges again
  - Inspect (A, B): 0 + 4 = 4 (no change)
  - Inspect (A, C): 0 + 3 = 3 (no change, 3 > 2)
  - Inspect (B, C): 4 + (-2) = 2 (no change)
  End of Pass 2: dist = {A: 0, B: 4, C: 2}

Pass 3 (Negative Cycle Check):
  - Check all edges one last time. No values decrease. 
  Conclusion: No negative cycles present.

Final Shortest Paths from A: {A: 0, B: 4, C: 2}

Summary Comparison

Metric Dijkstra’s Algorithm Bellman–Ford Algorithm
Core Strategy Greedy Search Dynamic Programming (Brute-Force Relaxation)
Time Complexity \(O((V + E) \log V)\) (with Min-Heap) \(O(V \cdot E)\)
Negative Weights Fails Handles successfully
Negative Cycles Cannot detect Detects explicitly on the \(V\)-th pass
Best Used For General routing, fast execution on positive graphs Graphs with negative traits, financial arbitrage detection