Dijkstra’s Shortest Path

Dijkstra’s algorithm solves the Single-Source Shortest Path (SSSP) problem: given a weighted graph and a source vertex, find the minimum-cost path to every other vertex. It drives OSPF routing, GPS navigation, and most practical pathfinding — and it is a textbook example of a correct greedy algorithm.

The Greedy Insight

At each step, Dijkstra picks the unvisited vertex with the smallest known distance and finalizes it. This is safe only because all edge weights are non-negative: once the cheapest way to reach a vertex is found, no future path — which would add non-negative cost to an already-larger distance — can improve it.

Edge Relaxation

The core operation is relaxing an edge (u, v) with weight w: if routing through u beats v’s current best, update it.

relax(u, v, w):
  if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u      # remember the predecessor for reconstruction

“Relax” means loosening a taut bound: if dist[v] was ∞ or too big, a shorter candidate path relaxes it down.

Algorithm

dist[s] = 0; dist[all others] = ∞
PQ = min-heap of (dist, vertex), seeded with (0, s)
while PQ not empty:
  (d, u) = extract-min
  if d > dist[u]: continue          # stale entry — already improved
  for each (v, w) in neighbors(u):
    relax(u, v, w); if improved, push (dist[v], v)

The priority queue always hands over the global smallest unsettled distance — that is what guarantees correctness. Skipping stale entries keeps a vertex from being processed twice.

Complexity

The binary-heap version is the standard: simple, cache-friendly, and fast for the sparse graphs that dominate real systems.

Dijkstra vs Bellman-Ford vs BFS vs A*

Use BFS when edges are unweighted (hops are cheaper than Dijkstra). Use Bellman-Ford when negative weights exist or you must detect negative cycles. Use A* when a good lower-bound heuristic exists and you want one target rather than all vertices.

Edge Cases

• Disconnected graphs: unreachable components keep dist = ∞; the result is still correct.
• Dense graphs: when E ≈ V², the O(V²) array version beats the heap version — heap operations cost log V each.
• Zero-weight edges: fine — distances simply don’t grow, and each vertex is still finalized once.
• Negative weights: Dijkstra can return wrong answers, because a negative edge can make an already-finalized vertex cheaper later. This is the single most common trap — verify non-negativity, or switch to Bellman-Ford.

Real-World Applications

• GPS navigation — fastest route over a road network.
• OSPF routing — each router computes its forwarding table with Dijkstra.
• Game AI — pathfinding on tile maps with movement costs (often upgraded to A*).
• Network latency optimization — minimum-latency routes over a measured topology.

Worked Example

Find the shortest paths from S on the graph below:

     2       3
S ————— A ————— T
 \            ^
  4     1     |
   ———— B ————+

Initialize: dist = {S:0, A:∞, B:∞, T:∞}, PQ = [(0, S)]

Extract (0, S):  relax S→A: dist[A]=2 ✓   relax S→B: dist[B]=4 ✓
Extract (2, A):  relax A→T: dist[T]=5 ✓
Extract (4, B):  relax B→T: 4+1=5 → not < 5, no change
Extract (5, T):  done — every reachable vertex finalized.

Final: dist = {S:0, A:2, B:4, T:5}
Shortest path S→T: S → A → T, cost 5

Note the key moment: when B was extracted at distance 4, its edge to T (cost 1) could only tie the existing 5, not beat it — so Dijkstra correctly kept S→A→T. Had the B–T edge been weight 0, B would have improved T and the parent pointer would flip to B.

Practice Trajectory

1. Hand-run Dijkstra on a 5-vertex weighted graph, writing out dist and parent after every extraction.
2. Implement the binary-heap version with stale-entry skipping; verify no vertex is processed twice.
3. Construct a graph with one negative edge and demonstrate the wrong answer — then fix it with Bellman-Ford.
4. Compare the array-based and heap-based versions on a complete (dense) graph and record where O(V²) wins.
5. Reconstruct the actual path from parent pointers and confirm it matches the finalized distances.

When It’s the Right Tool