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.

The Greedy Insight

At each step, pick the unvisited vertex with smallest known distance and “finalize” it. This greedy choice is safe because all edge weights are non-negative — once we’ve found the cheapest way to reach a vertex, no future path can improve it.

Edge Relaxation

The core operation is relaxing an edge (u, v, w):

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w    // found a better path!
    parent[v] = u

Step-by-Step Example

Graph: S --(2)--> A --(3)--> T
       |                     ^
       +-----(4)--> B --(1)--+

Initialize: dist = {S:0, A:∞, B:∞, T:∞}

Extract S (dist=0):
  Relax S→A: dist[A] = 0+2 = 2  ✓
  Relax S→B: dist[B] = 0+4 = 4  ✓

Extract A (dist=2):
  Relax A→T: dist[T] = 2+3 = 5  ✓

Extract B (dist=4):
  Relax B→T: dist[T] = min(5, 4+1) = 5  no change

Extract T (dist=5): done.
Shortest path: S → A → T, cost = 5

Complexity

Implementation	Time	Space
Simple array (dense)	O(V²)	O(V)
Binary heap PQ	O((V + E) log V)	O(V)
Fibonacci heap	O(E + V log V)	O(V)

Limitations

Requires non-negative weights — negative weights break the greedy assumption. Use Bellman-Ford instead.
Not for negative cycles — undefined behavior; use Bellman-Ford to detect them.
Dense graphs may favor the O(V²) array-based version.

Real-World Applications

GPS navigation: Finding the fastest route between cities
OSPF routing protocol: Internet routers use Dijkstra to compute forwarding tables
Game AI: Pathfinding on tile maps with movement costs
Network latency optimization: Finding minimum-latency routes