= Synchronous Bellman-Ford recurrence
{c}
{title2=$D_k(v)=\min\{D_{k-1}(v),\min_{(u,v)\in E}(D_{k-1}(u)+w_{uv})\}$}
For the single-source problem, let $D_k(v)$ be the minimum cost of a <directed walk> from $s$ to $v$ using at most $k$ <edges>. Set $D_0(s)=0$ and $D_0(v)=\infty$ for $v\ne s$, use $\infty+c=\infty$ for finite $c$, and let a <minimum> over an empty <set> be $\infty$. Then
$$
D_k(v)=\min\left\{D_{k-1}(v),\ \min_{(u,v)\in E}\bigl(D_{k-1}(u)+w_{uv}\bigr)\right\}.
$$
Every entry on the right comes from the previous round, requiring separate old and new arrays. The proof is the last-<edge> decomposition: a permitted <directed walk> either already uses at most $k-1$ <edges>, or ends with some $u\to v$ after a prefix using at most $k-1$. Conversely, each candidate describes a permitted <directed walk>. This <dynamic programming> viewpoint gives an exact meaning to every intermediate label, even when negative-cost <directed cycles> exist. Apply the formula to the source too: its initial zero is not a permanent constraint.
If no negative-cost <directed cycle> is reachable from $s$, removing repeated-<vertex> portions of a <directed walk> cannot increase its cost. Whenever a destination is reachable, some shortest <directed path> therefore uses at most $|V|-1$ <edges>, and $D_{|V|-1}(v)=\delta(s,v)$. Unreachable <vertices> keep distance $\infty$. For in-place passes, every finite label still comes from a discovered <directed walk>; moreover, pass $k$ has offered every prefix of length $k$ of a shortest <directed path>, regardless of scan order. Its labels can improve faster than the synchronous labels, while the same $|V|-1$ upper bound on passes remains valid. This is why repeated local corrections eventually settle a global <shortest path problem>.
Back to article page
