= All-to-one Bellman-Ford recurrence
{c}
{title2=$d_i^{(k)}=\min\{d_i^{(k-1)},\min_{(i,j)\in E}(c_{ij}+d_j^{(k-1)})\}$}
Keep the original all-to-one orientation of the <Bellman inequalities>: $d_i^{(k)}$ concerns routes \i[from] $i$ \i[to] a fixed sink $r$, and $c_{ij}$ belongs to the original <directed edge> $i\to j$. Initialize $d_r^{(0)}=0$ and $d_i^{(0)}=\infty$ for $i\ne r$. The synchronous <dynamic programming> recurrence is
$$
d_i^{(k)}=\min\left\{d_i^{(k-1)},\ \min_{(i,j)\in E}\bigl(c_{ij}+d_j^{(k-1)}\bigr)\right\}.
$$
It prepends the first <edge> of a route instead of appending the last: $d_i^{(k)}$ is the minimum cost of a <directed walk> from $i$ to $r$ using at most $k$ <edges>. In particular, improving $d_j$ can improve labels on incoming <directed edges> $i\to j$. The same original <directed edge> therefore updates its tail in this convention, whereas single-source <edge relaxation> updates its head.
If no negative-cost <directed cycle> can reach $r$, $|V|-1$ rounds suffice for every distance to $r$, and $d_r^{(k)}=0$ automatically. This hypothesis concerns <directed paths> \i[from the cycle to the sink], not paths from the sink to the cycle. In the base example with its original arrows and sink $T$, the distances in order $(S,A,B,C,T)$ are $(7,3,5,2,0)$. Once $C\to A$ of weight $-4$ is added, $S,A,B,C$ instead have distance $-\infty$ to $T$, while $T$ keeps distance $0$ and $U$ keeps $\infty$.
More generally, $\delta(i,r)=-\infty$ precisely when $i$ can reach a negative-cost <directed cycle> that can reach $r$. Thus the affected <vertices> are the ancestors of such a <directed cycle>. A negative-cost <directed cycle> unable to reach $r$ is irrelevant. Reversing all arrows makes $r$ a single source, turns these ancestors into descendants, and makes the detection and forward <graph search> above directly applicable. The right panel of the figure uses that reversal with sink $S$; its distances to $S$ equal the left panel's distances from $S$.
Do not force the root to remain zero outside the hypothesis. Consider the two <directed edges> $r\to a$ of cost $0$ and $a\to r$ of cost $-1$, with sink $r$. The recurrence gives $d_a^{(1)}=-1$ and $d_r^{(2)}=-1$: the latter records one lap of a negative-cost <directed cycle> through $r$. Repetition makes both unrestricted distances $-\infty$. Clamping $d_r$ at zero and omitting its update would instead leave the stationary labels $(d_r,d_a)=(0,-1)$, concealing that behaviour. Initialization specifies the cost of the empty <directed walk>; it does not forbid cheaper nonempty returns to the root. Cycle detection must test every relevant <directed edge>, including those whose relaxation updates the root.
Back to article page
