 Solution

ID: 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:

(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:

after edge (1, 2) (1, 3) (2, 4) (3, 5) (5, 4) d_{1} 00000 d_{2} 33333 d_{3} \infty 2222 d_{4} \infty \infty 665 d_{5} \infty \infty \infty 44

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 gives

allowed edges 01234 d_{1} 00000 d_{2} \infty 3333 d_{3} \infty 2222 d_{4} \infty \infty 655 d_{5} \infty \infty 444

Both conventions reach the same shortest distances. The algorithm's eponyms are Richard Bellman and L. R. Ford Jr..

 New to topics? Read the docs here!