Question

Just like the previous problem, but this time with the Bellman-Ford algorithm.

Short answer

The table that illustrates the Bellman-Ford algorithm’s values:

Step-by-step solution

Explain Bellman’s Ford Algorithm

Bellman-Ford algorithm marks the source vertex and marks all the distance of all the vertices as infinity. As the algorithm runs, when each vertex is visited, the distance between the vertices is calculated and the lowest distance values are updated at each iteration. The graph may contain negative weights.

Show a table showing the intermediate distance values of all the nodes.

(a)

Consider the given graph ,

Set S as the starting node.

In the zeroth iteration, set all the vertices values as$\infty$. At the first iteration, the path from S to A is calculated by checking all the possibilities from all the nodes. The table is updated with all the incoming vertices.

Likewise, for each iteration, the source to the particular vertex distance is updated.

The table that shows the intermediate values is as follows,

Therefore, The table showing the intermediate distance values is obtained.