What is Dijkstra's algorithm?
Dijkstra finds the shortest path from one starting node to every other node in a graph, as long as no edge
has a negative weight. It keeps a frontier of nodes it can reach but hasn't finished with yet, and on
every step it expands whichever frontier node is currently cheapest to reach — never a farther one first.
- Frontier
- The set of discovered-but-not-yet-finalized nodes, each with a best-known distance so far
- Finalized
- Once a node is popped from the frontier, its shortest distance is locked in for good
- Relax
- Check whether reaching a neighbor through the node you just popped beats its current best distance
Why Dijkstra at all?
Picture a road trip planner. From your starting town, it always drives next to whichever unvisited town is currently cheapest to reach — not the nearest by hops, the cheapest by total distance so far.
The moment it arrives at a town this way, it locks in that town's price and never reconsiders it. Anything reached later can only be farther, because every road still costs something to drive — so a "later" arrival can never undercut a price you already locked in.
Every pop locks in a price. Every relax only ever lowers a price still in play.
What kinds of problems does it solve?
Four common shapes. The loop never changes — pop the cheapest frontier node, relax its neighbors, repeat. Only what "cost" means, and when you stop, changes.
Shortest distance to every node
Run the loop until the frontier is empty. Every node ends up finalized with its true shortest distance from the source — useful for "how long until a signal reaches every server in the network?"
Once every node is finalized, the largest distance is the total travel time.
Cheapest path between two nodes
You can stop the moment the target node is popped — everything after that would only be more expensive. No need to finish finalizing the whole graph.
T only finalizes once nothing cheaper can still be found.
Costs that aren't a running total
"Cost" doesn't have to mean sum-of-weights. Swap in "largest single step along the way" and the exact same loop now solves a minimax path — the shape that shows up in effort- and rising-water-style grids.
Same pop-and-relax loop — only how two costs combine has changed.
Maximizing instead of minimizing
Probabilities multiply, and bigger is better, so flip the comparison: always pop the frontier node with the highest score, and relax by multiplying instead of adding.
Highest score wins the pop, multiplying replaces adding — the loop itself doesn't care.
Two ways to pick "cheapest next"
The algorithm is really BFS with the queue swapped out for a structure that always hands you the cheapest item, not just the oldest one. How you build that structure is the only real choice.
Linear scan
Keep distances in a plain array. Each round, scan every unvisited node to find the smallest distance —
simple to write, O(V) per pop, O(V²) overall. Fine for dense or small graphs.
Same finalized order as a heap — just a slower way to find the minimum each round.
function dijkstraLinear(graph: Map, start: string) {
const dist = new Map([[start, 0]]);
const done = new Set();
while (done.size < graph.size) {
let current: string | null = null;
for (const node of graph.keys()) {
if (done.has(node)) continue;
const d = dist.get(node) ?? Infinity;
if (current === null || d < (dist.get(current) ?? Infinity)) current = node;
}
if (current === null || dist.get(current) === Infinity) break;
done.add(current); // finalized — never revisited
for (const [neighbor, weight] of graph.get(current) ?? []) {
const candidate = (dist.get(current) ?? Infinity) + weight;
if (candidate < (dist.get(neighbor) ?? Infinity)) dist.set(neighbor, candidate);
}
}
return dist;
}
Min-heap
Keep the frontier in a min-heap keyed on distance. Popping the cheapest node is O(log V) instead
of a full scan, bringing the total down to O(E log V) — the standard choice for sparse graphs.
The heap hands over the minimum directly — no scanning needed.
function dijkstraHeap(graph: Map, start: string) {
const dist = new Map([[start, 0]]);
const heap = new MinHeap<[string, number]>((a, b) => a[1] - b[1]);
heap.push([start, 0]);
while (!heap.isEmpty()) {
const [node, d] = heap.pop(); // cheapest frontier entry
if (d > (dist.get(node) ?? Infinity)) continue; // stale entry, skip
for (const [neighbor, weight] of graph.get(node) ?? []) {
const candidate = d + weight;
if (candidate < (dist.get(neighbor) ?? Infinity)) {
dist.set(neighbor, candidate);
heap.push([neighbor, candidate]); // enqueue, priority = distance
}
}
}
return dist;
}
Where it works — and where it breaks
Dijkstra leans on one quiet assumption: once a node is popped, nothing discovered later can ever beat it. That's only true when every edge weight is zero or positive.
Works when every edge is non-negative
A later path can only add more distance on top of what's already spent, never subtract from it — so the cheapest frontier node really is done the moment it's popped.
Breaks the moment a weight goes negative
A node can be popped and locked in cheaply, and only afterward does a path through a negative edge turn up that would have beaten it. Dijkstra never revisits a finalized node, so it keeps the wrong answer.