= Solution
First run <breadth-first search>, ignoring weights, to obtain the minimum number of <edges> $h(v)$ from the source to each reachable <vertex>. Then compute weighted distances only along <edges> that advance one breadth-first layer:
``
d[source] = 0; all other d[v] = infinity
for u in nondecreasing BFS-layer order:
for each outgoing edge (u,v):
if h[v] == h[u]+1:
if d[u]+w(u,v) < d[v]:
d[v] = d[u]+w(u,v)
predecessor[v] = u
``
Unreachable vertices keep distance $\infty$. For an <undirected graph>, scan both orientations of each <edge>.
To justify discarding other routes, a <shortest path> can be taken simple because every weight is positive. A simple path of $r\leq n-1$ edges has weight in
$$
[r,r(1+1/n)]\subseteq[r,r+1).
$$
Every path with at least $r+1$ edges weighs at least $r+1$. Consequently every minimum-weight path must also have the minimum possible number of edges: this is <minimum-hop dominance for nearly unit weights>.
A minimum-hop path to $v$ uses exactly $h(v)$ edges. Every prefix of such a path must itself have minimum hop count, since replacing a longer prefix by a shorter one would shorten the whole route. Hence it advances from layer $j$ to layer $j+1$ at every step. The retained edges form a <Directed acyclic graph>, ordered by $h$. The displayed <dynamic programming> recurrence therefore finds the cheapest of all minimum-hop paths, which by the preceding bound is a true <shortest path>.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms-hop-bands.png]
{title=Disjoint weight bands for simple paths with different hop counts}
With an <adjacency list>, both the <breadth-first search> and the layer-ordered relaxations take \b[$O(n+m)$ time and $O(n+m)$ total storage], where $m=|E|$. The queue order from breadth-first search already supplies the layer order; no sorting or priority queue is needed. This improves the usual $O((n+m)\log n)$ binary-heap Dijkstra bound and is linear in the input size.
Back to article page
