Dijkstra's Algorithm

The classic shortest-path algorithm — Branch & Bound made elegant. A* with zero intuition, and still guaranteed optimal

The Simplest Explanation

Dijkstra is Branch & Bound with better bookkeeping — or equivalently, A* with no sense of direction ( $h = 0$ everywhere).

The idea in one sentence: always extend the cheapest path you have so far. It looks only backward at actual cost incurred ( $g$ ), never forward. Like water flooding outward from the source, it reaches nodes in order of their true cheapest distance.

$f(n) = g(n) + \underbrace{h(n)}_{=\,0} = g(n)$

Remember This

Dijkstra = pick the unvisited node with the smallest $g$ . Once a node is visited ("colored black"), its shortest distance is final — because all edge costs are positive, no detour can ever improve it.

From Branch & Bound to Dijkstra

Branch & Bound extends the cheapest partial path each step. It works: always refining the cheapest partial solution guarantees that when a complete solution beats all remaining estimates, it's optimal. But it keeps every partial path as a separate node in a search tree — the same city appears in dozens of partial paths.

Dijkstra (1959) cleans this up:

Keep one copy of each node in a single graph
Store one $g$ -value and one parent pointer per node
When a cheaper route to a node is found, just update its $g$ and re-point its parent

Same algorithmic heart, dramatically less memory.

The Algorithm

Assign $g = 0$ to start, $g = \infty$ to every other node; all nodes white (unvisited)
While unvisited nodes remain:
- Pick the cheapest white node $n$
- Color it black (visited) — its distance is now final
- For each white neighbor $m$ $m$ : relax edge $(n,m)$ $(n, m)$ :
  - if $g(n) + c(n,m) < g(m)$ , set $g(m) = g(n) + c(n,m)$ and parent $(m) = n$
Stop when the goal turns black; reconstruct the path via parent pointers

Why 'Black Means Final' Works

When node $n$ is chosen as cheapest among all white nodes, any alternative route to $n$ must pass through some other white node $w$ with $g(w) \geq g(n)$ — and since edges cost $\geq 0$ , that route costs $\geq g(n)$ . No improvement possible. This argument requires non-negative edge costs; negative edges break Dijkstra.

Interactive Trace

Watch Dijkstra flood outward from S to goal D, updating parents whenever a cheaper route appears:

Dijkstra TraceStep 0 / 5

Current (cheapest unvisited)

White — tentative g

Black — g finalized

Shortest Path

Initialize: every node gets g = ∞ except the start node, which gets g = 0. All nodes start white (unvisited).

g = 0

g = ∞

Key Observations

Cheapest-first ordering: after visiting S, node A ( $g=2$ ) beats B ( $g=5$ ) even though B was generated first.
Parent repointing: B's parent changes from S to A when $2+1 = 3$ undercuts $5$ . Dijkstra handles this gracefully because each node exists once.
No Case-3 problem: once black, a node's $g$ is never revised again — unlike A*, which may need to reopen closed nodes.

Where Dijkstra Sits in the Family

Algorithm	Picks by	Direction	Optimal?
BFS	fewest hops	backward (hops)	Yes, unweighted only
Branch & Bound / UCS	cheapest partial path $g$	backward ( $g$ )	Yes
Dijkstra	cheapest single node $g$	backward ( $g$ )	Yes
Best-First Search	smallest $h$	forward ( $h$ )	No
A*	smallest $f = g + h$	both	Yes, admissible $h$

Dijkstra explores blindly in all directions like flood fill. On a map going south from Chennai, it will explore half of Chennai before heading toward Mahabalipuram. Adding a heuristic $h$ converts it into A* — same skeleton, plus direction.

Complexity

Property	Value
Complete?	Yes (finite graph)
Optimal?	Yes, for non-negative edge costs
Time	$O((V + E)\log V)$ with binary heap
Space	$O(V)$ — one entry per node

Compare BFS's $O(b^d)$ tree explosion: Dijkstra's single-copy trick caps memory at one slot per distinct node.

QuizDijkstra's algorithm is a special case of A* with which heuristic?

QuizWhy can Dijkstra finalize a node (color it black) without ever revisiting it?

QuizWhat happens if some edges have NEGATIVE cost?