= Solution
Start with $(d[1],d[2],d[3],d[4])=(0,\infty,\infty,\infty)$. With in-place <edge relaxation>, the <Bellman-Ford algorithm> makes the following changes during its first lexicographic pass:
$$
\begin{array}{c|c|c}
\text{edge}&\text{improved entry}&\text{new value}\\\hline
(1,2)&d[2]&6\\
(1,3)&d[3]&2\\
(3,2)&d[2]&5\\
(3,4)&d[4]&3\\
(4,2)&d[2]&4
\end{array}
$$
The next pass makes no change; any remaining fixed-count passes also make none. Thus the final vector is \b[$(0,4,2,3)$]. These are sequential updates within a pass, rather than the simultaneous values of the <Synchronous Bellman-Ford recurrence>.
Back to article page
