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 d, and fill in the two-dimensional memorization array M[0..n, V] (provided below, where n = 5 is the number of nodes and V = {a, b, c, d, e} is the set of nodes in the graph). Each array entry should have the shortest path length and the immediate successor node (e.g., 8/e). Your answers should include the completed memorization table and for each node the shortest path and its path length in the following format: Shortest path from x to d: x y z d (path length = 8). (Note path length is the sum of the weights of edges in the path.)

Memoization table: 5-2 9