Algorithms from zero
Dijkstra''''s algorithm: weighted shortest paths
Last lesson, BFS gave you shortest paths for free—but only because every edge counted the same. Put a price tag on each edge (this road costs 1, that road costs 7) and BFS breaks: it minimizes the number of edges, not the total cost. A 2-edge route can cost far more than a 3-edge detour. Dijkstra’s algorithm fixes this. Instead of a plain queue that pops vertices in arrival order, it uses a min-priority-queue that always pops the vertex with the smallest tentative distance so far. Each pop “settles” a vertex—locks in its final shortest distance—and then “relaxes” its outgoing edges, lowering its neighbors’ tentative distances. It is BFS upgraded for weights, and it powers real routing: maps, networks, anything where moving costs differ.
After this lesson you can implement Dijkstra’s algorithm with a binary-heap min-priority-queue. You understand the two core operations: settle (pop the closest unsettled vertex and lock its distance as final) and relax (if dist[u] + w(u,v) < dist[v], lower dist[v] and record parent[v] = u). You maintain dist[] and parent[] so you can reconstruct a concrete cheapest path. You know the lazy-deletion trick: a binary heap has no decrease-key, so you push duplicate entries and skip stale pops. You understand—and can explain why—Dijkstra is correct only with non-negative weights, and that negative edges require Bellman-Ford instead. You know BFS is the special case where all weights equal 1. Cost: O((V+E) log V) time, O(V) space.
The weighted shortest path question
In a weighted graph, every edge carries a number—its weight or cost. The length of a path is the sum of its edge weights, not the count of edges. The shortest path from a source to a target is the path with the smallest total cost. We want, for every reachable vertex, that minimum cost plus a concrete route.
Why BFS is not enough
BFS pops vertices in arrival order (FIFO), which equals distance order only when all edges cost the same. With mixed weights, a vertex that is few edges away might be expensive, and a vertex many edges away might be cheap. We need to always expand the cheapest frontier next, not the nearest-in-edges frontier. That is the one change Dijkstra makes: swap the FIFO queue for a min-priority-queue keyed by tentative distance.
Settle and relax: the two operations
Dijkstra keeps a tentative distance dist[v] for every vertex (start at infinity, except dist[source] = 0). It repeats two steps until the queue is empty:
- Settle: pop the unsettled vertex
uwith the smallestdist[u]. Its distance is now final—no cheaper route toucan exist. Mark it settled. - Relax: for each outgoing edge
u -> vof weightw, check whether going throughubeats the best route known tov. Ifdist[u] + w < dist[v], then updatedist[v] = dist[u] + w, setparent[v] = u, and pushvinto the queue with its new key.
The settle invariant is the heart of the proof: when a vertex is popped as the minimum, every other route to it must pass through some still-larger tentative distance, so it cannot be cheaper. This is exactly why non-negative weights are required (more below).
Example graph (directed, weighted)
Adjacency list (vertex -> [neighbor, weight]):
A: [B:4, C:1]
B: [E:4]
C: [B:2, D:5]
D: [E:2]
E: [F:3]
F: []
Visual (arrows show direction, numbers are weights):
4
A ------> B
| |
1| |4
v 2 v 3
C ------> E ------> F
| ^
5| 2|
v |
D --------+Note the trap the direct edge A->B sets: it costs 4, but the detour A->C->B costs 1+2 = 3. Dijkstra must discover the cheaper route through C.
Worked relaxation trace (source = A)
Start with dist[A]=0, everything else infinity. The min-heap holds (distance, vertex) pairs.
heap = [(0,A)] dist: A=0 B=inf C=inf D=inf E=inf F=inf
Pop (0,A). Settle A. Relax A's edges:
A->B (4): 0+4=4 < inf -> dist[B]=4, parent[B]=A, push (4,B)
A->C (1): 0+1=1 < inf -> dist[C]=1, parent[C]=A, push (1,C)
heap = [(1,C),(4,B)] dist: A=0 B=4 C=1 D=inf E=inf F=inf
Pop (1,C). Settle C. Relax C's edges:
C->B (2): 1+2=3 < 4 -> dist[B]=3, parent[B]=C, push (3,B) (cheaper!)
C->D (5): 1+5=6 < inf -> dist[D]=6, parent[D]=C, push (6,D)
heap = [(3,B),(4,B),(6,D)] dist: A=0 B=3 C=1 D=6 E=inf F=inf
Pop (3,B). Settle B. Relax B's edges:
B->E (4): 3+4=7 < inf -> dist[E]=7, parent[E]=B, push (7,E)
heap = [(4,B),(6,D),(7,E)] dist: A=0 B=3 C=1 D=6 E=7 F=inf
Pop (4,B). B is already settled -> STALE, skip. (lazy deletion)
heap = [(6,D),(7,E)]
Pop (6,D). Settle D. Relax D's edges:
D->E (2): 6+2=8 < 7? No (8 >= 7) -> no update
heap = [(7,E)]
Pop (7,E). Settle E. Relax E's edges:
E->F (3): 7+3=10 < inf -> dist[F]=10, parent[F]=E, push (10,F)
heap = [(10,F)]
Pop (10,F). Settle F. No outgoing edges.
heap = [] Done.
Final distances: A=0 B=3 C=1 D=6 E=7 F=10
parent: A=null B=C C=A D=C E=B F=ETwo things to notice. First, B was relaxed twice: tentatively 4 via A, then improved to 3 via C. The stale (4,B) entry stayed in the heap and got skipped when popped. Second, the direct edge A->B (cost 4) lost to the detour A->C->B (cost 3)—relaxation found the cheaper route.
Reconstructing the concrete path A -> F
Walk parent[] backward from the target, then reverse:
start at F path = [F] parent[F]=E
go to E path = [F, E] parent[E]=B
go to B path = [F, E, B] parent[B]=C
go to C path = [F, E, B, C] parent[C]=A
go to A path = [F, E, B, C, A] parent[A]=null -> stop
reverse path = [A, C, B, E, F]The cheapest path is A -> C -> B -> E -> F, total cost 10, matching dist[F]=10.
BFS is Dijkstra with all weights = 1
If every edge weight is 1, “smallest tentative distance” equals “fewest edges,” and the min-priority-queue degenerates into BFS’s FIFO order. So BFS is the unit-weight special case of Dijkstra. Dijkstra is the generalization that handles arbitrary non-negative weights.
A min-heap (binary heap) for the priority queue
We need a structure that returns the smallest tentative distance fast. A binary min-heap gives O(log n) push and pop. It has no efficient decrease-key, so we will use lazy deletion instead.
1
class MinHeap {
2
constructor() { this.items = []; }
3
size() { return this.items.length; }
4
5
push(item) { // item = [distance, vertex]
6
const a = this.items;
7
a.push(item);
8
let i = a.length - 1;
9
while (i > 0) { // sift up to keep min at the root
10
const parent = (i - 1) >> 1;
11
if (a[parent][0] <= a[i][0]) break;
12
[a[parent], a[i]] = [a[i], a[parent]];
13
i = parent;
14
}
15
}
16
17
pop() { // remove and return the smallest
18
const a = this.items;
19
const top = a[0];
20
const last = a.pop();
21
if (a.length > 0) {
22
a[0] = last;
23
let i = 0; const n = a.length;
24
while (true) { // sift down to restore heap order
25
let smallest = i;
26
const l = 2 * i + 1, r = 2 * i + 2;
27
if (l < n && a[l][0] < a[smallest][0]) smallest = l;
28
if (r < n && a[r][0] < a[smallest][0]) smallest = r;
29
if (smallest === i) break;
30
[a[smallest], a[i]] = [a[i], a[smallest]];
31
i = smallest;
32
}
33
}
34
return top;
35
}
36
}
- L5 Each item is [distance, vertex]; we order by item[0], the distance.
- L9 Sift up: bubble the new item toward the root until its parent is smaller.
- L18 pop() always returns the smallest-distance pair: the closest frontier vertex.
- L24 Sift down: push the moved last element back down to its correct level.
- L27 Compare both children and swap with the smaller, repeating until settled.
Dijkstra with the heap, dist[], and parent[]
1
function dijkstra(source, adj) {
2
const dist = {};
3
const parent = {};
4
for (const v in adj) dist[v] = Infinity; // unknown = infinity
5
dist[source] = 0; // source is 0 from itself
6
parent[source] = null;
7
8
const settled = new Set();
9
const heap = new MinHeap();
10
heap.push([0, source]);
11
12
while (heap.size() > 0) {
13
const [d, u] = heap.pop(); // closest unsettled vertex
14
if (settled.has(u)) continue; // stale entry: skip (lazy deletion)
15
settled.add(u); // u's distance is now FINAL
16
17
for (const [v, w] of adj[u]) { // relax each outgoing edge
18
if (dist[u] + w < dist[v]) {
19
dist[v] = dist[u] + w; // cheaper route to v found
20
parent[v] = u; // remember the breadcrumb
21
heap.push([dist[v], v]); // push, do NOT decrease-key
22
}
23
}
24
}
25
return { dist, parent };
26
}
- L4 Every vertex starts at infinity: no route known yet.
- L5 The source costs 0 to reach from itself.
- L8 settled = vertices whose final distance is locked. Drives the skip below.
- L13 If u is already settled, this is a stale duplicate; ignore it.
- L14 Settling u commits dist[u] as final: the settle invariant.
- L17 Relaxation test: does routing through u beat the best known to v?
- L18 Lower dist[v] only when strictly cheaper, so we never inflate a distance.
- L20 No decrease-key: push a fresh (smaller) entry; the old one becomes stale.
Reconstructing a concrete path
1
function reconstructPath(target, parent) {
2
const path = [];
3
let cur = target;
4
while (cur !== null && cur !== undefined) {
5
path.push(cur); // collect target back to source
6
cur = parent[cur]; // step to the predecessor
7
}
8
path.reverse(); // flip to read source -> target
9
return path;
10
}
- L4 null marks the source; undefined means the target was never reached.
- L5 We gather vertices in reverse: target first, source last.
- L8 Reverse to get the natural source-to-target direction.
Running it on the example graph
A note on the priority queue
For clarity you could replace the binary heap with a sorted-array PQ (scan for the minimum each pop). It is simpler to read but gives O(V²) overall, fine for small graphs. The binary heap is what delivers the O((V+E) log V) bound stated below; production code often uses a Fibonacci heap (O(V log V + E)) or a d-ary heap, but a binary heap is the standard practical choice.
1
adj = { A:[B4,C1], B:[E4], C:[B2,D5], D:[E2], E:[F3], F:[] };
2
dist[A]=0; rest=inf; heap=[(0,A)];
3
pop min -> settle -> relax outgoing edges;
Time complexity: O((V + E) log V)
Each vertex is settled exactly once. To settle, we pop the heap; with lazy deletion the heap can hold up to one entry per relaxation, so up to O(E) entries, but its size is bounded by the number of pushes. Each push and each pop costs O(log of heap size) = O(log V) (the heap never holds more than O(E) entries, and log E = O(log V) because E < V²). Summed:
- Settling all vertices: V pops, each O(log V) = O(V log V).
- Relaxing all edges: each edge relaxation may push once, E pushes, each O(log V) = O(E log V).
Total: O((V + E) log V). On a connected graph E >= V - 1, so this is often written O(E log V).
sorted-array PQ : O(V^2) -> good for dense graphs (E ~ V^2)
binary heap : O((V+E) log V) -> good for sparse graphs (E ~ V)
Fibonacci heap : O(V log V + E) -> best asymptotic, rarely neededSpace complexity: O(V)
dist[] holds up to V entries, parent[] up to V, the settled set up to V. The heap with lazy deletion can transiently hold up to O(E) stale entries, but the bookkeeping arrays are O(V). The dominant working set is O(V) (heap is O(E) in the worst case, which equals O(V) on sparse graphs).
Why non-negative weights are required (the settle invariant breaks otherwise)
Dijkstra’s correctness rests on this claim: when a vertex u is popped as the heap minimum, dist[u] is final. The argument: any other path to u must leave the settled region through some unsettled vertex x whose tentative distance is >= dist[u] (else x would have been popped first). Since edges only add cost, the full path through x costs at least dist[x] >= dist[u]. So no cheaper route to u exists.
That argument silently assumes edges never reduce the running total. A negative edge breaks it:
A --1--> B
A --4--> C
B --(-3)--> C (negative edge!)
Dijkstra from A:
Settle A. Relax: dist[B]=1, dist[C]=4.
Pop (1,B) -> settle B (LOCKED). Relax B->C: 1 + (-3) = -2 < 4
-> dist[C] = -2.
Pop next... but C might already be settled at the wrong value
in a larger graph, and B's "final" distance can itself be
undercut later by a negative edge feeding back.
True shortest A->C = A->B->C = 1 + (-3) = -2, but Dijkstra's
settle step can commit a vertex BEFORE a later negative edge
would have lowered it. The invariant fails.A settled vertex can no longer be improved—but a negative edge is exactly an improvement arriving after settling. So Dijkstra can return wrong answers on negative weights. For graphs with negative edges, use Bellman-Ford (O(V*E), relaxes all edges V-1 times and detects negative cycles). Dijkstra trades that generality for speed, and the price is the non-negativity requirement.
What does Dijkstra use instead of BFS's FIFO queue, and why?
What is the relaxation step for an edge u -> v of weight w?
A binary heap has no efficient decrease-key. How does the standard Dijkstra implementation cope?
Why does Dijkstra require non-negative edge weights?
How is BFS related to Dijkstra?
In the lesson graph (A:[B4,C1], B:[E4], C:[B2,D5], D:[E2], E:[F3]), what is dist[F], the cheapest total cost from A to F?
Why this works
Why settle then relax, in that order? Settling a vertex is the act of trusting its tentative distance as final. That trust is only valid for the current heap minimum, because every alternative route must pass through an equal-or-larger tentative distance (non-negative weights guarantee it). Once u is trusted, relaxing its edges propagates that final value outward to neighbors. Relaxing before settling would let unfinalized, possibly-wrong distances spread.
Common mistake
Relaxing or re-settling a stale pop. With lazy deletion the heap holds duplicates. If you forget the if (settled.has(u)) continue; guard, you will process an outdated entry: re-settle an already-final vertex and relax its edges with a larger, stale distance. That wastes work and—if combined with overwriting dist—can corrupt results. Always skip a pop whose vertex is already settled.
Edge cases
Unreachable vertices. If a vertex sits in no path from the source, it is never pushed, so its dist stays Infinity and it has no parent. Reconstruction from such a target stops immediately (cur is undefined) and returns a list that does not start at the source. Check dist[target] !== Infinity before reporting a path, and say “no path” otherwise.
More practice
Negative weights -> Bellman-Ford. The moment any edge can be negative, drop Dijkstra. Bellman-Ford relaxes every edge V-1 times in O(V*E) and, on a Vth pass, detects negative cycles (where “shortest path” is undefined because you can loop to -infinity). It is slower but tolerates negatives. Real systems pick Dijkstra when costs are physical and non-negative (distance, latency, money) and Bellman-Ford when costs can be credits or refunds.
Explain how Dijkstra computes weighted shortest paths, what settle and relax mean, why lazy deletion is used with a binary heap, and why the algorithm needs non-negative weights.
Dijkstra’s algorithm finds shortest paths from a source on a weighted graph with non-negative edge weights. It generalizes BFS by swapping the FIFO queue for a min-priority-queue keyed by tentative distance.
Two operations: settle the popped minimum (its dist is now final), then relax its outgoing edges—if dist[u] + w < dist[v], lower dist[v] and set parent[v] = u.
Bookkeeping: dist[] for costs, parent[] for the breadcrumb trail. Walk parent[] backward from the target and reverse to rebuild a concrete cheapest path.
Lazy deletion: a binary heap has no decrease-key, so push duplicate entries on each improvement and skip any pop whose vertex is already settled.
Time: O((V + E) log V). Space: O(V).
The boundary: non-negative weights only. Settling commits a distance as final, but a negative edge could lower it afterward, breaking the settle invariant—use Bellman-Ford for negatives. BFS is the special case where every weight is 1.