02
Shortest Paths: Dijkstra's Algorithm
Chapter 2 • Advanced
120 min
Shortest Paths: Dijkstra's Algorithm
Problem Statement
Find shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights.
Dijkstra's Algorithm
Greedy Strategy
At each step, select the unvisited vertex with minimum distance from source.
Algorithm Steps
- Initialize distances: dist[source] = 0, others = ∞
- Use priority queue (min-heap) to track vertices
- While queue not empty:
- Extract vertex u with minimum distance
- Mark u as visited
- For each neighbor v of u:
- If dist[v] > dist[u] + weight(u,v):
- Update dist[v] = dist[u] + weight(u,v)
- Add/update v in priority queue
Implementation
python.js
import heapq
def dijkstra(graph, start):
"""
Dijkstra's algorithm for shortest paths.
graph: adjacency list [(neighbor, weight), ...]
Time: O((V + E) log V), Space: O(V)
"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
visited = [False] * n
# Priority queue: (distance, vertex)
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, weight in graph[u]:
if not visited[v]:
new_dist = d + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
Shortest Path Reconstruction
python.js
def dijkstra_with_path(graph, start, end):
"""Dijkstra with path reconstruction"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
parent = [-1] * n
visited = [False] * n
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
if u == end:
break
for v, weight in graph[u]:
if not visited[v]:
new_dist = d + weight
if new_dist < dist[v]:
dist[v] = new_dist
parent[v] = u
heapq.heappush(pq, (new_dist, v))
# Reconstruct path
if dist[end] == float('inf'):
return None, float('inf')
path = []
current = end
while current != -1:
path.append(current)
current = parent[current]
return path[::-1], dist[end]
Why Greedy Works
- Optimal Substructure: Shortest path to v contains shortest path to u
- Greedy Choice: Vertex with minimum distance is guaranteed to have shortest path
Limitations
- Non-negative weights only: Fails with negative weights
- No negative cycles: Cannot handle negative cycles
Time Complexity
- With binary heap: O((V + E) log V)
- With Fibonacci heap: O(E + V log V)
- Dense graphs: O(V²) with array-based implementation
Practice Problems
- Shortest path from source to all vertices
- Shortest path between two specific vertices
- K shortest paths
- Network delay time
- Cheapest flights with at most K stops