Bellman-Ford algorithm

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.