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.

-1 -4 61- b)-( d t 3 d) -2 4 3