Question

12 8 4 6 4 6 2. Consider the same network as in Problem 1. Assume node r is the only destination in the network. Use a table to show the computation process of the Bellman-Ford algorithm. Each row in the table corresponds to one iteration of the algorithm, and each column is a pair (D (A), H(A)) where D,(A) is the cost from node i to A and Hi(A) is the next hop on the path from i to A. In each iteration, each node broadcasts its distance vector to its neighbors if there has been a change in its distance vector.

Answer 1

Let us start with a brief introduction of the bellman ford algorithm.

Bellman Ford's algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph. It depends on the following concept: Shortest path contains at most n−1 edges, because the shortest path couldn't have a cycle.

So why shortest path shouldn't have a cycle ?
There is no need to pass a vertex again, because the shortest path to all other vertices could be found without the need for a second visit for any vertices.

Algorithm Steps:

• The outer loop traverses from 0 : n−1.
• Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".

Since Bellman Ford is a single source shortest path algorithm, so let us pick one vertex to start with. Let that vertex be z.

Node initial (Distance,parent) 1st (Distance,parent) 2nd (Distance,parent) 3rd (Distance,parent) 4th(Distance,parent) 5th(Distance,parent) 6th (Distance,parent) 0,null (INFINITE,null) INFINITE,null) INFINITE,null) INFINITE,null) INFINITE,null) (INFINITE,null) (0,null (8,z) (12.2) (0,null (8z) (12,z) (15,v) (0,null (8,z) (12.2) (0,null) (8z) (12,z) (19.y) (0,null) (8,z) 12.z) (15,v) (11x) (14,x) (14,v) (0,null) (8,z) (12,z) 15,v) 15,v) 15,v) (14,x) (14,v) (14,x) (14,v) (14,x) (21.t) (14,x) 14,v) (14,x) (14,v)

Each column represents the distance from the source node and the parent from which the node gets the distance. We iterate n-1 = 7-1 = 6 times.

4 5 2 4 3 2 8 0

NOTE:

• This is a general representation of the working of the bellman-ford algorithm, according to your specific need you can change how the column structure is represented but the basic working principle will remain the same.
• This is a graph representing the paths. The arrow in green shows the selected path.

Credits: The images provided are from google sheets and draw.io websites. I have provided them for a better understanding of the problem.

Please provide a feedback and clarify if further if you wish to.  
FURTHER READING: Try reading Floyd–Warshall's Algorithm for finding the shortest path between all pairs of vertices.

It also looks like your question is dependent on some previous question, in such cases please provide the complete question. Also try to restructure the table according to your specific need.

Thanks, Happy to help.