= Solution
Use a <dynamic programming state> indexed by an <edge> budget. Put $D_0(s)=0$ and $D_0(v)=\infty$ for $v\ne s$, then for $r=1,\ldots,k$ compute
$$
\boxed{D_r(v)=\min\left(D_{r-1}(v),\ \min_{(u,v)\in E}\{D_{r-1}(u)+w(u,v)\}\right).}
$$
Every route using at most $r$ <edges> either already uses at most $r-1$, or ends with some <edge> $(u,v)$ whose preceding route uses at most $r-1$. Conversely every finite candidate in the displayed equation is attained by such a route. This proves the <hop-bounded shortest-route recurrence> by <induction> on $r$, even when weights are negative.
In each round, copy the previous distance row and relax every <edge> into the new row, always reading from the old row. An in-place pass would allow several new <edges> in one round and violate the <edge> budget. Store a predecessor record for every selected candidate, either a carry to $(r-1,v)$ or the incoming <edge> from $(r-1,u)$. Following records backwards from $(k,t)$ and reversing the collected <edges> returns the actual optimum route; an infinite final distance means no feasible route exists.
Only <vertices> incident to an <edge>, together with $s,t$, need distance fields. In a graph representation whose <edges> reference <vertex> records, initialise those fields by visiting both endpoints of every <edge>, then $s,t$; repeated initialisations are harmless. In each round, first copy old fields to new fields by another complete endpoint pass, and only then begin the relaxation pass. Copying the same endpoint several times before any relaxation also does no harm. Thus each round costs $O(m+1)$, with no scan of isolated <vertices>, and for $m,k\ge1$ the total is \b[$O(km)$ time]. An implementation that instead initialises full arrays for all <vertices> has the conventional bound $O(|V|+km)$. For $k=0$ or no <edges>, only the empty route $s=t$ can succeed.
To realise reconstruction without a dense table, associate a persistent route record with each finite distance. A successful relaxation in round $r$ creates a record containing the new <edge> and a pointer to the old round's route record at its source; a carry shares its record. All reads use old-round records. At most $km$ such records are created, taking $O(km)$ space, and the returned chain has at most $k$ <edges>. Distances alone need only two fields per relevant <vertex>.
Here “route” uses the standard edge-budget shortest-path convention permitting repeated <vertices>; a bounded budget prevents an arbitrarily long negative-cycle traversal. If “path” instead requires <vertex> simplicity with unrestricted negative weights, this recurrence does not enforce that extra restriction. With nonnegative weights, removing cycles gives a simple optimum within the same budget.
Back to article page
