Lesson 25
Dijkstra's Shortest Paths
Greedy exploration with a priority queue finds the cheapest route.
01Why it matters & the intuition
Google Maps, network routing (OSPF) and game AI pathfinding descend from Dijkstra's algorithm. It is also where heaps and graphs meet.
Think of it like…
Water poured at the start node flows along pipes whose lengths are the edge weights. The water reaches each junction first along the shortest route — Dijkstra simulates that by always advancing the closest unsettled node.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- discovered / in container
- processing now
- finished
03Key ideas
Tentative distances
Start at 0 for the source and ∞ elsewhere. Distances only ever decrease as better routes are found.
Settle the closest
Pop the unsettled node with the smallest distance (a min-heap). Its distance is now final.
Relax edges
For each edge u → v with weight w: if dist[u] + w < dist[v], update dist[v] and push v into the heap.
No negative weights
The greedy 'settled is final' argument breaks with negative edges. Use Bellman-Ford for those.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function dijkstra(n: number, edges: [number, number, number][], src: number): number[] {
const adj: [number, number][][] = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) adj[u].push([v, w]);
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
// [distance, node] pairs; a sorted-array stand-in for a min-heap keeps the idea visible.
const pq: [number, number][] = [[0, src]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift()!;
if (d > dist[u]) continue; // stale entry
for (const [v, w] of adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push([dist[v], v]);
}
}
}
return dist;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| With binary heap | O((V + E) log V) | — |
| With simple array scan | O(V²) | — |
| Space | — | O(V + E) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Network delay time
Write network_delay(times, n, k). times[i] = [u, v, w] is a directed edge from node u to v taking w ms; nodes are 1..n. A signal starts at k. Return the time for all nodes to receive it, or -1 if some never do.