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 |