The Single-Source Shortest Paths Problem

Problem Statement

Given a weighted, directed graph $G = (V, E)$ with weight function $w: E \to \mathbb{R}$ and a designated source vertex $s \in V$, find the shortest path (minimum total weight) from $s$ to every other vertex.

Shortest-path weight from $u$ to $v$:

$\delta(u, v) = \begin{cases} \displaystyle\min_{p: u \leadsto v} w(p) & \text{if a path exists} \\[8pt] \infty & \text{otherwise} \end{cases}$

where $w(p) = \sum_{i=1}^{k-1} w(v_i, v_{i+1})$ for path $p = v_1, v_2, \ldots, v_k$.

A shortest path from $u$ to $v$ is any path $p$ satisfying $w(p) = \delta(u, v)$. Shortest paths are not necessarily unique; there may be multiple paths with the same minimum weight.

Variants of Shortest-Path Problems

Variant	Input	Output
SSSP (Single-Source)	$G, w, s$	$\delta(s, v)$ for all $v \in V$
SDSP (Single-Destination)	$G, w, t$	$\delta(v, t)$ for all $v$
SPSP (Single-Pair)	$G, w, s, t$	$\delta(s, t)$
APSP (All-Pairs)	$G, w$	$\delta(u, v)$ for all pairs

SDSP reduces to SSSP on $G^T$. SPSP has no known algorithm asymptotically faster than SSSP in the worst case. APSP can be solved by $|V|$ iterations of SSSP or by dedicated algorithms (Floyd-Warshall, Johnson).

Assumptions and Edge Cases

• No negative-weight cycles reachable from $s$. If a negative cycle is reachable, you can loop forever, decreasing path weight without bound: $\delta(s, v) = -\infty$ for any vertex on the cycle, and the problem is ill-defined.
• Positive-weight cycles are never part of a shortest path: removing such a cycle strictly reduces the total weight. Hence shortest paths can be assumed simple (no vertex repeated).
• Zero-weight cycles do not affect path weight; they can be removed without changing the result. So we assume shortest paths have at most $|V|-1$ edges.
• Distances are undefined (or $-\infty$) if a negative-weight cycle is reachable on the path to that vertex.

Optimal Substructure

Shortest paths exhibit optimal substructure: any subpath of a shortest path is itself a shortest path.

Proof: Let $p = v_1 \leadsto v_k$ be a shortest path, and let $v_i \leadsto v_j$ be any contiguous subpath. If there were a shorter path $p'$ from $v_i$ to $v_j$, replacing the subpath with $p'$ would produce a $v_1 \leadsto v_k$ path strictly shorter than $p$, contradicting optimality of $p$.

This property is the foundation for dynamic programming (Floyd-Warshall) and greedy (Dijkstra) approaches.

The Relaxation Operation

All shortest-path algorithms in this course share a common subroutine: relaxation of an edge. The idea is to test whether going through $u$ improves the current estimate for $v$:

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

• $d[v]$ is the current estimate of $\delta(s, v)$.
• $\pi[v]$ is the predecessor of $v$ on the current candidate shortest path.
• Initialisation sets $d[s] = 0$ and $d[v] = \infty$ for all $v \neq s$, and all $\pi[v] = \text{NIL}$.

Upper-bound property: After any sequence of relaxations, $d[v] \ge \delta(s, v)$ always holds. Relaxation never makes estimates too low; it only lowers overestimates towards the true value.

Predecessor Subgraph

The edges $(\pi[v], v)$ for all $v \in V \setminus \{s\}$ with $\pi[v] \neq \text{NIL}$ form the predecessor subgraph $G_\pi$. At any point during execution, $G_\pi$ is a tree rooted at $s$ (a “shortest-path tree” in progress). When the algorithm terminates correctly, the unique path in $G_\pi$ from $s$ to any reachable $v$ is a shortest path in $G$.

To reconstruct a path: start at $v$, follow $\pi$ pointers backwards until reaching $s$, then reverse the sequence.

Algorithm Landscape

All SSSP algorithms differ only in the order in which they relax edges:

Algorithm	Constraint	Edge Order	Time
BFS	Unweighted ($w=1$ for all edges)	By distance levels	$\Theta(V+E)$
DAG-SSSP	DAG only	Topological order	$\Theta(V+E)$
Dijkstra	$w \ge 0$	Greedy by $d[u]$	$O((V+E)\log V)$
Bellman-Ford	None (no neg. cycles)	All edges $V-1$ times	$O(VE)$

Worked Example: Relaxation Sequence

Graph: $s \to a$ (5), $s \to b$ (3), $a \to b$ (1), $b \to c$ (2).

Operation	$d[s]$	$d[a]$	$d[b]$	$d[c]$
Initialise	0	$\infty$	$\infty$	$\infty$
RELAX(s,a)	0	5	$\infty$	$\infty$
RELAX(s,b)	0	5	3	$\infty$
RELAX(a,b)	0	5	3	$\infty$
RELAX(b,c)	0	5	3	5

Final: $\delta(s,a)=5$, $\delta(s,b)=3$, $\delta(s,c)=5$ (path $s \to b \to c$).

The order of relaxation matters: if $(a,b)$ were relaxed before $(s,b)$, we would temporarily set $d[b]=6$, but then $(s,b)$ corrects it to 3. Bellman-Ford handles this by relaxing everything repeatedly; Dijkstra avoids it by always processing vertices in increasing distance order.

Summary

Concept	Description
$\delta(s, v)$	Minimum path weight from $s$ to $v$
Optimal substructure	Subpath of shortest path is shortest
Relaxation	if d[v] > d[u] + w(u,v): update
Upper bound	$d[v] \ge \delta(s,v)$ always
Predecessor $\pi$	Encodes shortest-path tree
Max simple path length	$\lvert V \rvert - 1$ edges

Past paper questions: y2024p1q9 (opportunities, relaxed costs), y2023p1q9 (SSSP variants).