Consider the directed graph shown below. Run the Bellman-Ford shortest path algo
ID: 3808460 • Letter: C
Question
Consider the directed graph shown below. Run the Bellman-Ford shortest path algorithm 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.)
Show the intermediate steps of computing the shortest path length
-4Y3 -2 3 s 6 c 3 a bExplanation / 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.