Dijkstra's Algorithm
The Intuition
Imagine you're a delivery driver starting from your warehouse. You have a city map with roads of different lengths. Your goal is to find the shortest route to every intersection in the city. Here's your strategy: always drive to the unvisited intersection that's closest to the warehouse, not closest to where you are right now, but closest to home by total distance.
You start at the warehouse. You look at all roads leaving it: one is 3 miles to intersection A, another is 7 miles to intersection B. You drive to A first (it's closer to home). From A, you discover a 2-mile road to intersection C. Now C is 3 + 2 = 5 miles from home. That's still closer than B's 7 miles, so you visit C next. From C, you find more roads, update more distances. You always pick the next closest-to-home intersection.
Why does this work? Because all road lengths are positive. Once you've driven to an intersection via the shortest known route, no future discovery can beat it. Any other path would have to go through an intersection that's farther from home, and adding more positive-length roads only makes it longer. So the first time you visit any intersection, you've already found the shortest path. That's the guarantee.
The min-heap is your prioritized to-do list. It holds intersections sorted by their tentative distance from home. You pop the smallest, explore its roads, and push any improved distances back in. Sometimes the heap contains stale entries, intersections you already visited via a shorter route. Just skip those when you pop them. If the distance you popped is worse than what you've already recorded, throw it away and grab the next one.
Shortest path in weighted graphs with non-negative weights, network routing, navigation systems, or any problem asking for minimum cost paths.
- Negative edge weights (use Bellman-Ford)
- Unweighted graph (BFS is simpler and sufficient)
- Need all-pairs shortest path (use Floyd-Warshall)
Variations:
- Single-target: Stop early when the target node is popped from the heap.
- With path reconstruction: Track predecessors to rebuild the shortest path.
- 0-1 BFS: When weights are only 0 or 1, use a deque instead of a heap for O(V + E) time.
- Single node graph (distance is zero)
- Target node is unreachable from the source
- Graph contains zero-weight edges
- Graph has negative weights (Dijkstra produces incorrect results)
Key Points
- •Finds shortest path from source to all vertices in weighted graphs
- •Uses a min-heap (priority queue) to always process the nearest unvisited node
- •Does NOT work with negative edge weights. Use Bellman-Ford instead
- •Lazy deletion: skip nodes already finalized when popped from heap
- •Can reconstruct path by tracking predecessors
Code Template
1 import heapq
2
3 def dijkstra(graph, start, n):
4 """Shortest paths from start. graph[u] = [(v, weight), ...]"""
5 dist = [float('inf')] * n
6 dist[start] = 0
7 heap = [(0, start)] # (distance, node)
8
9 while heap:
10 d, u = heapq.heappop(heap)
11 if d > dist[u]:
12 continue # stale entry
13
14 for v, weight in graph[u]:
15 new_dist = dist[u] + weight
16 if new_dist < dist[v]:
17 dist[v] = new_dist
18 heapq.heappush(heap, (new_dist, v))
19
20 return dist
21
22 def dijkstra_with_path(graph, start, end, n):
23 """Shortest path with reconstruction."""
24 dist = [float('inf')] * n
25 dist[start] = 0
26 prev = [-1] * n
27 heap = [(0, start)]
28
29 while heap:
30 d, u = heapq.heappop(heap)
31 if d > dist[u]:
32 continue
33 if u == end:
34 break
35 for v, weight in graph[u]:
36 new_dist = dist[u] + weight
37 if new_dist < dist[v]:
38 dist[v] = new_dist
39 prev[v] = u
40 heapq.heappush(heap, (new_dist, v))
41
42 # Reconstruct path
43 path = []
44 node = end
45 while node != -1:
46 path.append(node)
47 node = prev[node]
48 return path[::-1] if dist[end] != float('inf') else []Common Mistakes
- Using with negative edge weights (incorrect results)
- Not using lazy deletion (processing stale entries from the heap)
- Forgetting to initialize distances to infinity