Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 7 / b / Solution

The intermediate states of the Bellman-Ford algorithm depend on edge order. Specify in-place edge relaxation in lexicographic directed-edge order:Starting with $(0,\infty ,\infty ,\infty ,\infty )$, the first pass changes the vector as follows; omitted relaxations make no change:The next pass makes no change, allowing early termination. If all $|V|-1=4$ passes are performed, passes two through four retain $(0,3,2,5,4)$.

For the synchronous convention, where every relaxation reads only the previous row, the Synchronous Bellman-Ford recurrence instead givesBoth conventions reach the same shortest distances. The algorithm's eponyms are Richard Bellman and L. R. Ford Jr..