Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to every other vertex in a weighted graph, provided all weights are non-negative. It's BFS generalized to handle weights — the queue becomes a priority queue keyed by current best distance.

The algorithm

Maintain a distance array initialized to $\infty$ except for the source (distance 0). Push the source into a min-heap keyed by distance. Loop:

1. Pop the closest vertex $u$. 2. If we've already finalized $u$, skip. 3. Otherwise, for each neighbor $v$, if $\text{dist}[u] + w(u, v) < \text{dist}[v]$, update $\text{dist}[v]$ and push $v$ into the heap.

Complexity

With a binary heap, $O((V + E) \log V)$ — every edge causes at most one heap push, and each heap operation is $O(\log V)$. With a Fibonacci heap, you can do $O(E + V \log V)$, but the constant factor makes it rarely worth it in practice.

Why no negative edges

Dijkstra greedily finalizes the closest unvisited vertex. With negative edges, the "finalized" distance might still be improvable through a longer-looking path that traverses a negative edge. Use Bellman-Ford ($O(VE)$) when negatives are possible.

Path reconstruction

Track each vertex's predecessor at the moment its distance is updated. After running Dijkstra, follow predecessors backward from the destination to reconstruct the path.

Common application: road networks

Real-world map routing uses Dijkstra extended with bidirectional search, A* (Dijkstra plus a heuristic), and contraction hierarchies (precomputed shortcuts). The core algorithm is unchanged.