 Synchronous Bellman-Ford recurrence

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$. ThenEvery 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.