PQ = min-priority-queue with (dist[v], v) for all v
while PQ not empty:
u = PQ.extract_min() // greedy choice
for each edge (u,v,w):
if dist[u] + w < dist[v]: // relaxation
dist[v] = dist[u] + w
parent[v] = u
PQ.decrease_key(v, dist[v])
§2 — The Idea, Step by Step
Start — the cheapest route across town. Type a destination into a maps app and it hands you the fastest way there, not just the one with the fewest turns. Picture a city of street corners joined by roads, where each road has a cost — minutes in traffic, or kilometres. You want the lowest total cost from your home corner to every other corner. Dijkstra’s trick is patient and greedy: always step next to the nearest corner you have not yet locked in, settle its best cost for good, then see whether reaching it opens up a cheaper way to its neighbours. Spread out from cheapest to dearest and you never overpay.
Build — named quantities and the one move that matters. A graph is corners (vertices, $V$) joined by roads (edges, $E$); every edge carries a weight $w(u,v)\ge 0$, its cost. Keep one number per corner, $\text{dist}[v]$ — the best total cost found so far from the source $s$. Start with $\text{dist}[s]=0$ and every other $\text{dist}[v]=\infty$. The whole algorithm is one repeated move called relaxation: for a road from $u$ to $v$, ask “is going through $u$ cheaper than what I had?” — if $\text{dist}[u]+w(u,v)<\text{dist}[v]$, lower $\text{dist}[v]$ to that sum. Worked example: roads $A\!\to\!B=4$, $A\!\to\!C=2$, $C\!\to\!B=1$. From $A$ you first set $\text{dist}[B]=4$ and $\text{dist}[C]=2$. But relaxing $C\!\to\!B$ gives $2+1=3<4$, so the true cheapest $A\!\to\!B$ is $3$, sneaking through $C$ — not the direct road.
Deepen — the greedy guarantee, and why no negatives. Which corner do you lock in next? Always the unsettled one with the smallest $\text{dist}$. A min-priority queue hands it over fast. The key promise (the greedy invariant): the moment a corner is pulled from the queue, its $\text{dist}$ is final and can never improve. Why? Any other route to it must pass through some corner that is still unsettled and therefore already at least as far — and since no edge has negative cost, a longer detour can only add cost, never claw it back. That last clause is the catch: with a negative edge a later road could undercut an already-locked corner, and the guarantee collapses (then you reach for Bellman–Ford instead). With a binary heap the bill is $V$ extract-min plus $E$ relaxations, each $O(\log V)$, giving $O((V+E)\log V)$. Strip the weights to all-$1$ and the priority queue degenerates to a plain queue — that is exactly breadth-first search.
Try this in the panel above. The animated panel is a generic step-through demo of an algorithm trace, so use it to feel the “settle the nearest, then relax its neighbours” rhythm. Press ▶│ (Next) to advance one operation and ◀ (Back) to retrace it, watching each value lock in before the next. Hit ▶ Play and drop the speed to 0.25× so no step blurs past. Then drag the n slider to a new size and press ↻ Reset to launch a fresh trace from the top.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Greedy Invariant. At each step, the extracted vertex u has the final shortest distance. Proof: if there were a shorter path to u via an unvisited vertex w, then dist[w] >= dist[u] (since w was not extracted yet and all weights are non-negative) -- contradiction.
Step 2 -- Relaxation. Edge relaxation: if dist[u] + w(u,v) < dist[v], update dist[v]. Each edge (u,v) is relaxed at most once (when u is extracted). Correctness relies on non-negative weights -- negative weights can invalidate the greedy choice.
Step 3 -- Time with Binary Heap. V extract-min operations: O(V log V). E decrease-key operations: O(E log V). Total: O((V+E) log V). For dense graphs (E = O(V^2)): O(V^2 log V). Better to use simple array: O(V^2).
Step 4 -- Time with Fibonacci Heap. V extract-min: O(V log V) amortized. E decrease-key: O(E) amortized O(1) each. Total: O(E + V log V). Optimal for sparse graphs but Fibonacci heap has large constants -- rarely faster in practice.
Step 5 -- Why Non-negative Weights Required. With negative edge (u,v,w<0): when u is extracted, dist[v] may already be finalized. But later negative edge could give shorter path. Dijkstra's greedy choice fails. Use Bellman-Ford for negative weights.
Step 6 -- Applications. GPS routing (Google Maps, Apple Maps). Network routing protocols (OSPF). Video game pathfinding (A* = Dijkstra + heuristic). Social network shortest path. Flight booking (cheapest route). Robotics motion planning.
§4 — Frequently Asked Questions
What is edge relaxation? concept+
Relaxation checks if going through u improves the known shortest path to v. If dist[u] + w(u,v) < dist[v], then update dist[v]. The name comes from the analogy of a rubber band: you relax (shorten) the path estimate toward the true shortest path.
Why does Dijkstra fail with negative edges? concept+
Dijkstra's greedy invariant assumes: once a vertex is extracted from the priority queue, its distance is final. Negative edges can create shorter paths AFTER extraction. Example: u extracted with dist=5, but edge (u,v,-10) makes dist[v] = -5 which could improve already-extracted vertices.
How does Dijkstra relate to A* search? applied+
A* = Dijkstra + heuristic. Dijkstra's priority key = dist[u]. A*'s priority key = dist[u] + h(u) where h(u) is an admissible heuristic (estimated remaining distance). A* explores fewer nodes on average. Used in GPS navigation and game AI pathfinding.
What is the difference between Dijkstra and BFS for graphs? concept+
BFS: works on unweighted graphs (all edge weights = 1). Dijkstra: handles weighted graphs with non-negative weights. BFS is O(V+E). Dijkstra is O((V+E) log V). BFS is Dijkstra where all weights are 1 and the priority queue degenerates to a FIFO queue.
Why is Dijkstra O(V^2) with an adjacency matrix? nonobv+
With adjacency matrix, finding the minimum-dist unvisited vertex requires scanning all V vertices: O(V). Done V times: O(V^2). For dense graphs (E = O(V^2)), this beats the heap version O(V^2 log V). For sparse graphs (E = O(V)), use heap version O(V log V).
What is 0-1 BFS and when to use it? deep+
For graphs where edges have weight 0 or 1 only: use a deque. Weight-0 edges: push front. Weight-1 edges: push back. Gives O(V+E) shortest paths -- faster than Dijkstra O((V+E) log V). Used in problems where moving in one direction is free, another costs 1.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ Dijkstra works with negative edge weights.
✓ Dijkstra FAILS with negative edges. Use Bellman-Ford (O(VE)) or SPFA for negative weights. Dijkstra's greedy extraction assumption breaks with negatives.
✗ Dijkstra finds shortest path in O(V+E).
✓ Dijkstra with binary heap is O((V+E) log V). O(V+E) is BFS complexity for unweighted graphs. O(V^2) is Dijkstra with simple array on dense graphs.
✗ Re-inserting a vertex into the priority queue when a shorter path is found is equivalent to decrease-key.
✓ Lazy deletion (insert duplicate, skip if already processed) works but bloats the PQ to O(E) size and slows to O(E log E). True decrease-key O(log V) is faster but requires indexed PQ.
Implementation Errors
✗ Forgetting to check if extracted vertex was already processed.
✓ With lazy deletion approach, the same vertex may be in PQ multiple times. Must check: if dist[u] < extracted dist, skip this stale entry.
✗ Initializing all distances to 0 instead of INF.
✓ Source distance = 0. All others = infinity (INT_MAX or 1e18). Initializing to 0 makes Dijkstra think all vertices are already at distance 0 -- no relaxation happens.
✗ Using Dijkstra when edge weights can be negative.
✓ Dijkstra gives wrong answers for negative edges without any error. Always check: if graph has negative edges, use Bellman-Ford. Dijkstra with negative edges is a silent correctness bug.