Dijkstra's Shortest Path
Hard+110 XPFind the cheapest route through a weighted graph by always finalizing the closest node next.
No visualization loaded.
Watch
—
Press Run to begin.
Imagine a map of towns joined by roads, but now every road has a length (a 'weight') — some are long, some short. Dijkstra's algorithm finds the CHEAPEST total route from your start town to every other town, not just the one with the fewest roads. It keeps a running table called dist[] — its best-known cheapest distance to each town so far — and improves those numbers as it discovers shortcuts. The clever rule: always lock in the closest town you haven't finalized yet, because nothing you find later can ever beat it.
▸What does 'shortest path' mean when edges have weights?
Cheapest TOTAL, not fewest roads. Each edge has a cost (distance, time, money). The length of a path is the sum of its edge costs. So a route with three short roads can beat a route with one very long road. Dijkstra adds up the weights along the way and keeps the smallest sum to each node.
▸Why can't BFS handle weighted graphs?
BFS counts steps — it treats every edge as length 1, so it finds the path with the fewest edges. With weights, the fewest-edges path can be expensive. In our example A→B is one road of length 4, but A→C→B is two roads of length 2+1=3 — cheaper! BFS would wrongly pick the direct road. Dijkstra weighs the cost, so it spots the cheaper detour.
▸What is 'relaxing' an edge?
Relaxing edge u→v asks: 'Is going to v THROUGH u cheaper than my best-known way to v?' If dist[u] + weight(u,v) is smaller than the current dist[v], we lower dist[v] to that and remember u as v's parent. 'Relax' just means 'try to loosen / improve' the current best estimate — every improvement nudges dist[] closer to the truth.
▸Why always pick the CLOSEST unvisited node (the greedy step)?
Because once a node is the closest unfinalized one, no future path can do better. Any other route to it would have to pass through some node that's already farther away, so it could only add more cost. That guarantee is what lets Dijkstra 'finalize' a node forever the moment it picks it — it never has to second-guess a settled distance.
▸Why does it need a priority queue (min-heap)?
Every round it must grab the unvisited node with the smallest dist. Scanning all nodes each time is slow on big graphs. A min-heap (the heap lesson!) hands you the minimum in O(log n) and lets you push improved distances cheaply. That's what turns Dijkstra into O((V+E) log V) instead of O(V²).
▸Does it work with negative edge weights?
No. Dijkstra's whole guarantee — 'the closest unvisited node is final' — assumes adding an edge never makes a path cheaper. A negative edge could make a longer-looking route suddenly cheaper after you've already locked a node in, breaking the logic. For negative weights you need a different algorithm (Bellman-Ford).
How the work grows
O((V+E) log V) with a heap is good — the practical sorting speed. Each node is finalized once (V pops from the heap) and each edge is relaxed once (E pushes), and every heap operation costs about log V — so the work grows almost linearly with the graph times a small log factor. Space holds the distance table and the heap of frontier nodes.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.