All-to-one Bellman-Ford recurrence ($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 from $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 isIt 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 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.