Day 65: Graph Traversal Optimization & Shortest Path (Dijkstra)
Extend BFS shortest-path thinking to WEIGHTED graphs using Dijkstra's algorithm and a priority queue, and know when it breaks down.
Study
Concepts
Why plain BFS fails on weighted edges
BFS (Day 18) finds shortest paths correctly only because every edge has equal "cost" (1 hop) — the first time you reach a node via BFS is guaranteed to be via the fewest hops. With weighted edges (a road network where distances differ, a graph where "cost" is time or price), the fewest-HOPS path is not necessarily the LOWEST-COST path, so plain BFS gives wrong answers.
Dijkstra's algorithm generalizes BFS by replacing the FIFO queue with a MIN-PRIORITY QUEUE ordered by accumulated distance-so-far, always expanding the currently-cheapest-known unvisited node next — this greedy choice is provably correct as long as all edge weights are non-negative (a negative edge can make a "settled" node's distance wrong later, which is exactly why Dijkstra fails on negative weights and Bellman-Ford is needed instead).
The core loop and its complexity
Maintain a `distances` map (initialized to Infinity except the source, which is 0) and a min-heap of `[distance, node]`. Repeatedly pop the cheapest entry; if it is stale (a better distance was already found and this entry is an old, since-superseded one), skip it; otherwise, relax each neighbor (`if distances[node] + weight < distances[neighbor], update it and push the improved entry`). With a binary heap, this runs in O((V + E) log V) — the log V factor comes directly from heap push/pop operations, the same complexity class as Day 15's heap-adjacent structures.
A* (A-star) is Dijkstra with an added heuristic estimate of remaining distance to the target (e.g. straight-line distance on a map), which lets it explore more directly toward the goal instead of expanding outward in all directions equally — a common follow-up interview question once Dijkstra is understood solidly.
See It
Visualizations
Visualization
Dijkstra's core loop
a cheaper distance was already recorded for this node
update + push if a cheaper path through this node is found
Build It
Code Examples
Dijkstra's algorithm with a binary min-heap
class MinHeap {
#items = [];
get size() { return this.#items.length; }
push(item) { this.#items.push(item); this.#bubbleUp(this.#items.length - 1); }
pop() {
const top = this.#items[0];
const last = this.#items.pop();
if (this.#items.length) { this.#items[0] = last; this.#bubbleDown(0); }
return top;
}
#bubbleUp(i) {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.#items[parent][0] <= this.#items[i][0]) break;
[this.#items[parent], this.#items[i]] = [this.#items[i], this.#items[parent]];
i = parent;
}
}
#bubbleDown(i) {
const n = this.#items.length;
while (true) {
let smallest = i;
const [l, r] = [2 * i + 1, 2 * i + 2];
if (l < n && this.#items[l][0] < this.#items[smallest][0]) smallest = l;
if (r < n && this.#items[r][0] < this.#items[smallest][0]) smallest = r;
if (smallest === i) break;
[this.#items[smallest], this.#items[i]] = [this.#items[i], this.#items[smallest]];
i = smallest;
}
}
}
function dijkstra(graph, source) {
const distances = new Map([[source, 0]]);
const heap = new MinHeap();
heap.push([0, source]);
while (heap.size) {
const [dist, node] = heap.pop();
if (dist > (distances.get(node) ?? Infinity)) continue; // stale entry — skip
for (const [neighbor, weight] of graph.get(node) ?? []) {
const newDist = dist + weight;
if (newDist < (distances.get(neighbor) ?? Infinity)) {
distances.set(neighbor, newDist);
heap.push([newDist, neighbor]);
}
}
}
return distances;
}Remember
Key Takeaways
- Plain BFS only finds shortest paths on UNWEIGHTED (or equal-weight) graphs — weighted graphs need Dijkstra.
- Dijkstra swaps BFS's FIFO queue for a min-priority queue ordered by accumulated distance — same "expand outward" shape, different ordering.
- Correctness REQUIRES non-negative edge weights — negative edges break the greedy assumption and require Bellman-Ford instead.
- Stale heap entries (superseded by a since-found cheaper path) must be skipped on pop, not prevented on push — that check is easy to forget.
- Complexity is O((V+E) log V) with a binary heap — know this number and where the log V comes from (heap operations).
Do It
Practice
- 1Trace Dijkstra by hand on a 5-node weighted graph on paper before running the code, predicting the final distances map.
- 2Modify the implementation to also reconstruct the actual shortest PATH (not just distance) by tracking a "previous node" map.
- 3Explain, with a concrete 3-node example, why a negative edge weight can produce an incorrect result from Dijkstra.