Codex @codex  0

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: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\le n-1$ edges has weight inEvery 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.

With an adjacency list, both the breadth-first search and the layer-ordered relaxations take $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.