Dijkstra's Algorithm

BFS finds shortest paths when every edge counts as one step. But what if edges have weights — road lengths, flight costs, latencies? Now the path with the fewest edges is not necessarily the cheapest one: a direct 2-edge route of total weight 20 loses to a 3-edge route of total weight 12.

Dijkstra's algorithm solves the single-source shortest path problem on weighted graphs with non-negative edge weights: given a source s, it computes dist[v] — the minimum total weight of any path from s to v — for every vertex v at once.

The idea is a beautiful upgrade of BFS:

BFS uses a queue and processes vertices in order of number of edges from the source. Dijkstra uses a min-priority queue and processes vertices in order of total distance from the source.

That one change — replace the FIFO queue with a min-heap — turns BFS into Dijkstra.

Every vertex is in one of three states:

• Unreached — no path found yet; dist = ∞.
• Fringe — at least one path is known; dist holds the tentative (best-so-far) distance, and the vertex sits in the min-heap.
• Settled — dist is final; no shorter path can ever be found.

The main loop repeats two moves until the heap is empty:

1. Settle. Pop the fringe vertex u with the smallest tentative distance. That distance is now final (we'll see why below).
2. Relax. For every edge u → v of weight w: if dist[u] + w < dist[v], we just found a shorter way to reach v — update dist[v] = dist[u] + w, remember parent[v] = u, and push (dist[v], v) into the heap.

The greedy intuition: when u is the closest unsettled vertex, any other route to u would have to pass through some other unsettled vertex first — which is already farther away, and edges can only add non-negative weight on top of that. So no detour can beat dist[u]. This is exactly the same cut-style argument as Prim's MST — in fact the two algorithms are near-twins; only the quantity in the heap differs (total path length vs. single edge weight).

Run Dijkstra from vertex 1 on the same weighted graph as the MST chapters — but notice we now minimize path length, not tree weight. Step forward and backward with the ← / → arrow keys or the buttons below.

What to watch:

• Each vertex's d= label is its tentative distance — it only ever decreases, and freezes when the vertex turns green (settled).
• The min-heap panel always pops the smallest entry — that's the greedy choice. (If a fringe vertex's distance improved while it sat in the heap, its old entry would go stale and be skipped when popped — lazy deletion.)
• Green edges form the growing shortest-path tree: follow parent pointers backwards from any vertex to read off its actual shortest path.
• Compare with Prim on the same graph: Dijkstra settles 5 at distance 11 via 4, because 5 + 6 = 11 beats the direct 1→2→5 cost of 7 + 9 = 16.

Dijkstra's whole correctness rests on one assumption: once a vertex is settled, no shorter path to it can appear later. A negative edge breaks that promise.

Tiny counterexample with three vertices:

Dijkstra settles a first at dist = 2 (it's the closest). But the path s → b → a costs 3 + (−2) = 1 < 2 — too late: a is already settled and will never be re-examined. Wrong answer.

Rules of thumb:

• All weights ≥ 0 → Dijkstra (this chapter).
• Some weights < 0, no negative cycles → Bellman–Ford (next topic).
• All weights = 1 → plain BFS is simpler and faster.

The standard lazy-deletion version — instead of a true decrease-key operation, just push a fresh (dist, vertex) entry and skip stale ones when popped (the if d > dist[u]: continue line). This is exactly what the visualization runs, and it is the version to memorize: it needs nothing more than the standard library's priority queue.

Each vertex is settled exactly once. Each edge u → v is relaxed once (when u settles), and each successful relaxation pushes one heap entry — so the heap holds at most O(E) entries over the whole run.

• E pushes and up to E pops, each O(log E) = O(log V) (since E ≤ V², log E ≤ 2 log V).
• Total: O((V + E) log V) with a binary heap.
• Space: O(V + E) for the adjacency list, dist/parent arrays, and heap.

With a Fibonacci heap the bound improves to O(E + V log V), but constants make it rare in practice. For dense graphs (E ≈ V²) a heap-free O(V²) version — scan all vertices for the minimum each round — is actually faster.