= Bellman-Ford algorithm
{c}
For an all-to-one <shortest path problem> with root $r$, initialize $d_r^{(0)}=0$ and all other labels to infinity. Set $d_i^{(k)}=\min(d_i^{(k-1)},\min_{(i,j)\in A}\{c_{ij}+d_j^{(k-1)}\})$, keeping the root at zero. Induction identifies the labels with the shortest <directed paths> using at most $k$ <directed edges>. Without a reachable negative <directed cycle>, $|V|-1$ rounds suffice after removing <directed cycles> from a shortest walk. In-place or queue variants repeatedly relax incoming <directed edges> to an improved label. Labels may decrease multiple times, so this is a <label-correcting shortest-path algorithm>.
Back to article page
