1. Dijkstra's Algorithm

Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959, solves the single-source shortest-path (SSSP) problem on a weighted graph with non-negative edge weights. Starting from a source vertex \(s\), it determines the minimum-cost path to every vertex reachable from \(s\) in \(O((V + E) \log V)\) time (with a binary heap). Dijkstra's is arguably the most important greedy algorithm in graph theory: it underpins GPS navigation, internet routing protocols (OSPF), public transit planning, and network flow preprocessing ¹².

1.1 Problem Statement

Given a weighted directed graph \(G = (V, E, w)\) where \(w : E \to \mathbb{R}_{\geq 0}\) assigns non-negative real weights to edges, and a source \(s \in V\), find, for every vertex \(v \in V\):

Set \(\delta(s, v) = \infty\) if \(v\) is not reachable from \(s\).

1.2 The Algorithm

Dijkstra's algorithm greedily settles vertices in order of their current distance estimate. It maintains a min-priority queue \(Q\) keyed by \(d[v]\):

DIJKSTRA(G, w, s):
  for each v ∈ V:
    d[v] = ∞;  π[v] = NIL
  d[s] = 0
  Q = V (min-priority queue keyed by d)
  while Q ≠ ∅:
    u = EXTRACT-MIN(Q)        // settles u
    for each v ∈ Adj[u]:
      RELAX(u, v, w)

RELAX(u, v, w):
  if d[v] > d[u] + w(u, v):
    d[v] = d[u] + w(u, v)
    π[v] = u
    DECREASE-KEY(Q, v, d[v])

1.2.1 The Greedy Choice

At each step, Dijkstra extracts the unsettled vertex \(u\) with the smallest \(d[u]\) estimate and settles it — declares \(d[u]\) final. The key insight is that if all edge weights are non-negative, no future path through an unsettled vertex can improve the cost to \(u\): any such path would first have to pass through a vertex with \(d \geq d[u]\).

1.2.2 Correctness: Loop Invariant

At the start of each EXTRACT-MIN, for every vertex \(v \in S\) (already settled):

\(d[v] = \delta(s, v)\)

Proof (sketch): suppose the first vertex incorrectly settled is \(u\), with \(d[u] > \delta(s, u)\). Then there is a true shortest path \(s \leadsto y \to \cdots \to u\) where \(y\) is the last settled vertex on the path and \(( y, \cdots )\) are unsettled. By the inductive hypothesis \(d[y] = \delta(s, y)\) (correct). After relaxing \((y, z)\):

By non-negativity \(\delta(s, z) \leq \delta(s, u) < d[u]\), contradicting the fact that \(u\) was chosen as the minimum-key element over \(z\) ¹.

1.3 Complexity

For sparse graphs (\(E = O(V)\)), the binary-heap implementation gives \(O(V \log V)\). For dense graphs (\(E = O(V^2)\)), the \(O(V^2)\) array version is competitive. Fibonacci heaps achieve the theoretically optimal bound but carry large constants and are rarely used in practice ¹.

1.4 Why Non-Negative Weights?

The greedy settlement step depends critically on the fact that adding an unsettled vertex to a path cannot decrease its cost. If a negative edge \((u, v)\) exists, a path through an unsettled vertex might be cheaper than the current estimate, invalidating the invariant.

Counterexample with negative weight: \(s \to u\) with cost 5, \(s \to v\) with cost 3, \(v \to u\) with cost \(-10\). Dijkstra settles \(v\) first (\(d[v] = 3\)), then settles \(u\) with \(d[u] = 5\) — but the shortest path is \(s \to v \to u\) with cost \(-7\). Dijkstra fails.

For graphs with negative weights (but no negative cycles), use Bellman–Ford (\(O(VE)\)).

1.5 Relationship to Other Algorithms

Dijkstra and Prim differ only in their priority key: Dijkstra keys on the total path cost, while Prim keys on the single edge weight connecting a vertex to the current tree.

1.6 Applications

• GPS and mapping services (route planning)
• Internet routing (OSPF and IS-IS protocols)
• Flight path optimisation
• Network delay analysis
• Preprocessing for bidirectional shortest-path queries

1.7 Interactive Demo

The canvas below shows Dijkstra's algorithm on a 9×9 grid with random integer edge weights. Settled vertices are darkened; the priority queue frontier is shown in blue with their distance labels. After reaching the goal, the shortest path is highlighted in red.