Hop-bounded shortest-route recurrence ($D_r(v)=\min \{D_{r-1}(v),{\min }_{(u,v)\in E}(D_{r-1}(u)+w(u,v))\}$)

Let $D_r(v)$ be the minimum weight of a route from a fixed source to $v$ using at most $r$ edges; repeated vertices are permitted. Initialise $D_0$ to zero at the source and infinity elsewhere. Every feasible route either already uses at most $r-1$ edges or appends one edge to such a route, proving the displayed dynamic programming recurrence. Reading exclusively from the previous row enforces the edge budget. Negative cycles cause no unbounded objective because the budget is finite. Each round scans all edges, costing $O(m)$ when only edge-incident vertices and the specified endpoints are processed. With nonnegative weights, cycle removal gives an equally good or better simple path within the budget.