= Solution
The intermediate states of the <Bellman-Ford algorithm> depend on <edge> order. Specify in-place <edge relaxation> in lexicographic directed-edge order:
$$
(1,2),(1,3),(2,3),(2,4),(3,5),(5,2),(5,4).
$$
Starting with $(0,\infty,\infty,\infty,\infty)$, the first pass changes the vector as follows; omitted relaxations make no change:
$$
\begin{array}{c|ccccc}
\text{after edge}&d_1&d_2&d_3&d_4&d_5\\\hline
(1,2)&0&3&\infty&\infty&\infty\\
(1,3)&0&3&2&\infty&\infty\\
(2,4)&0&3&2&6&\infty\\
(3,5)&0&3&2&6&4\\
(5,4)&0&3&2&5&4
\end{array}
$$
The next pass makes no change, allowing early termination. If all $|V|-1=4$ passes are performed, passes two through four retain \b[$(0,3,2,5,4)$].
For the synchronous convention, where every relaxation reads only the previous row, the <Synchronous Bellman-Ford recurrence> instead gives
$$
\begin{array}{c|ccccc}
\text{allowed edges}&d_1&d_2&d_3&d_4&d_5\\\hline
0&0&\infty&\infty&\infty&\infty\\
1&0&3&2&\infty&\infty\\
2&0&3&2&6&4\\
3&0&3&2&5&4\\
4&0&3&2&5&4
\end{array}
$$
Both conventions reach the same shortest distances. The algorithm's eponyms are <Richard Bellman> and <L. R. Ford Jr.>.
Back to article page
