Shortest paths (Dijkstra)
We'll cover the following
Roads have different lengths, written "a-b:length". Find the shortest distance from the start to every node.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
src00
∞1
∞2
∞3
∞4
∞5
∞6
∞7
∞8
∞9
dist[i] is the best known distance from node 0. Only the source is known (0).
1 / 12
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O((V + E) log V) | O(V + E) | Each improved distance is a heap push. |
In Python
import heapq
def dijkstra(adj, src):
dist = {src: 0}; pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float('inf')): continue
for v, w in adj[u]:
if d + w < dist.get(v, float('inf')):
dist[v] = d + w
heapq.heappush(pq, (d + w, v))
return distSummary: say it in the interview
- Always settle the closest unsettled node next. Its distance is final because every other route starts from something at least as far away. Then try to improve its neighbours. A priority queue finds the closest node in log n.
- Time O((V + E) log V), space O(V + E). Each improved distance is a heap push.