Consider the directed graph shown below. Run the Bellman-Ford shortest path algo
ID: 3807924 • Letter: C
Question
Consider the directed graph shown below. Run the Bellman-Ford shortest path algorithm we studied in class to find the shortest path from each node to the node t. Specifically, fill in the two-dimensional memorization array M[0..n, V] (where n is the number of nodes and V is the set of nodes in the graph) with the shortest path length and the immediate successor node in each entry. Show the completed memorization table (with “shortest path length/immediate successor in each array entry, e.g., “8/d”) and, for each node, show the shortest path and its path length in the following format: “Shortest path from x to t: x – y – z – t (path length = 8)”. (Note path length is the sum of the weights of edges in the path.) You are encouraged to show the intermediate steps of computing the shortest path length for partial credit in case your answer is incorrect because of a mistake. When drawing a table of the two-dimensional array, align the columns in the order of s, a, b, c, d, and t, and the rows in an increasing order of i = 0 to 5; this will make the grading easier
4 a -1 -4 b)-- -(d v( t ) 3 8 ( d 3Explanation / Answer
Let source vertex be 0. Initialize all distances as infinite, except the distance to source itself.
S a b c d t
0 (First iteration i=0)
----------------------------------------------------------------
First Iteration give all shortest paths which are at most 1 edge long.
S a b c d t
0
---------------------------------------------------------------
0 -4
0 -4 -3 (i=1)
---------------------------------------------------------------
The second iteration guarantees to give all shortest paths which are at most 2 edges long
S a b c d t
0
-----------------------------------------------------------------
0 -4
0 -4 -3 (i=1)
---------------------------------------------------------------------
0 -5 -4 -3
0 -5 -6 -4 -3
0 -5 -6 -4 -4 (i=2)
------------------------------------------------------------------
The Third iteration guarantees to give all shortest paths which are at most 3 edges long.
S a b c d t
0
-----------------------------------------------------------------
0 -4
0 -4 -3 (i=1)
--------------------------------------------------------------------
0 -5 -4 -3
0 -5 -6 -4 -3
0 -5 -6 -4 -4 (i=2)
-------------------------------------------------------------------
0 -5 -6 -4 -9 -4
0 -5 -6 -4 -9 -6 (i=3)
------------------------------------------------------------------------
The algorithm processes all edges 2 more times. The distances are minimized after the third iteration, so fourth and fifth iterations don’t update the distances.
So it will
S a b c d t
0
-----------------------------------------------------------------
0 -4
0 -4 -3 (i=1)
--------------------------------------------------------------------
0 -5 -4 -3
0 -5 -6 -4 -3
0 -5 -6 -4 -4 (i=2)
-------------------------------------------------------------------
0 -5 -6 -4 -9 -4
0 -5 -6 -4 -9 -6 (i=3)
------------------------------------------------------------------------
0 -5 -6 -4 -9 -6 (i =4 )
--------------------------------------------------------------------------
0 -5 -6 -4 -9 -6 (i =5 )
--------------------------------------------------------------------------------------------------------------------------------------------
If you have any query, please feel free to ask.
Thanks a lot.