Dijkstra's Algorithm

Overview

Dijkstra’s algorithm solves the single-source shortest paths (SSSP) problem for directed or undirected graphs with non-negative edge weights ($w(u, v) \ge 0$ for all edges). It is a greedy algorithm: at each step, it selects the unprocessed vertex with the smallest current distance estimate, finalises it, and relaxes its outgoing edges.

Pseudocode

DIJKSTRA(G, w, s):
  for each v in G.V:
    v.d = ∞
    v.π = NIL
  s.d = 0
  S = ∅                              // set of finalised vertices
  Q = new PriorityQueue(G.V)          // keyed on v.d
  while Q not empty:
    u = EXTRACT-MIN(Q)
    S = S ∪ {u}
    for each v in G.Adj[u]:
      RELAX(u, v, w)                  // may call DECREASE-KEY on Q

The set $S$ tracks finalised vertices. It is not required for execution (the priority queue alone determines which vertex is processed next), but it is used in the correctness proof.

Greedy Intuition

Once a vertex $u$ has the smallest $d[u]$ among all vertices still in the priority queue, its distance is final. Why? Any alternative path to $u$ must enter $u$ from some other unprocessed vertex $x$. Since all edge weights are non-negative, the path via $x$ has cost at least $d[x] + \text{non-negative} \ge d[x] \ge d[u]$ (because $u$ was chosen as minimum). So $d[u]$ cannot be improved.

Worked Example

Same graph used in the Bellman-Ford notes: $V = \{A,B,C,D,E,F,G\}$, source $s = E$, all weights non-negative.

Edges: $E \to A:5$, $E \to F:7$, $E \to G:3$, $A \to B:1$, $A \to C:2$, $G \to F:3$, $C \to D:2$.

Iter	Extract	S	$d[A]$	$d[B]$	$d[C]$	$d[D]$	$d[E]$	$d[F]$	$d[G]$
Init	—	$\emptyset$	$\infty$	$\infty$	$\infty$	$\infty$	0	$\infty$	$\infty$
1	E	{E}	5	$\infty$	$\infty$	$\infty$	0	7	3
2	G	{E,G}	5	$\infty$	$\infty$	$\infty$	0	6	3
3	A	{E,G,A}	5	6	7	$\infty$	0	6	3
4	B	{E,G,A,B}	5	6	7	$\infty$	0	6	3
5	F	{E,G,A,B,F}	5	6	7	$\infty$	0	6	3
6	C	{E,G,A,B,F,C}	5	6	7	9	0	6	3
7	D	all	5	6	7	9	0	6	3

Extract order (by minimum $d$): E(0), G(3), A(5), B(6), F(6), C(7), D(9). Note that B and F both have $d=6$; tie-breaking is arbitrary. At each step, the extracted vertex’s distance is final: no later relaxation can reduce it.

Shortest path from $E$ to $D$: $E \to A \to C \to D$ (cost $5+2+2 = 9$).

Comparison with Bellman-Ford on the Same Graph

Bellman-Ford takes up to 7 iterations of relaxing all edges. On this graph it converges in 2 iterations (since the longest shortest path has 3 edges, but convergence can be faster depending on edge order). Dijkstra extracts exactly $|V| = 7$ vertices, each with one priority queue extract-min and neighbour relaxation. The extra overhead of the priority queue is offset by not scanning all edges on every iteration.

Running Time Analysis

Depends on the priority queue implementation:

PQ Implementation	EXTRACT-MIN	DECREASE-KEY	Total
Unsorted array	$O(V)$	$O(1)$	$O(V^2 + E)$
Binary heap	$O(\log V)$	$O(\log V)$	$O((V+E)\log V)$
Fibonacci heap	$O(\log V)$ amortised	$O(1)$ amortised	$O(V\log V + E)$

Derivation for binary heap: $|V|$ EXTRACT-MIN at $O(\log V)$ each; up to $|E|$ DECREASE-KEY at $O(\log V)$ each. Total: $O(|V|\log|V| + |E|\log|V|) = O((|V|+|E|)\log|V|)$.

For dense graphs where $|E| = \Theta(|V|^2)$, the array-based version ($O(|V|^2)$) may outperform the binary heap version ($O(|V|^2 \log |V|)$) due to lower constant factors. For sparse graphs, the heap methods are superior.

Comparison with Bellman-Ford

	Dijkstra	Bellman-Ford
Edge weights	$w \ge 0$ only	Any real
Technique	Greedy + PQ	DP / repeated relaxation
Time	$O((V+E)\log V)$	$O(VE)$
Negative cycle detection	N/A	Yes
Works on DAGs	Yes	Yes

When Dijkstra Fails on Negative Edges

Consider $s \to a$ (weight 2), $s \to b$ (weight 3), $a \to b$ (weight $-2$). Dijkstra from $s$: extracts $a$ first ($d[a]=2$), marking it final. Then relaxes $(a,b)$: $d[b] = 2 + (-2) = 0$. But $b$‘s distance is now 0, whereas $a$ was finalised at 2 — the true shortest distance to $a$ might actually be via $b$ if we could go backwards (in a graph with more edges). The algorithm cannot backtrack to correct $a$, so it produces wrong results. Bellman-Ford correctly handles this case.

Summary

Property	Detail
Type	Greedy algorithm
Weight constraint	$w(u,v) \ge 0$ for all edges
Data structure	Priority queue (min-heap)
Invariant	$v.d = \delta(s,v)$ for all $v \in S$
Binary heap time	$O((V+E)\log V)$
Fibonacci heap time	$O(V\log V + E)$
Fails on	Negative edge weights

Past paper questions: y2024p1q9 (opportunities, Dijkstra variants), y2023p1q9 (bidirectional Dijkstra), y2025p1q10(d) (Dijkstra with different priority queues).