= Hop-bounded shortest-route recurrence
{title2=$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.
Back to article page
