$(50)[$Bellman$-$Ford shortest paths: algorithm tracing$]$ Consider the directed graph shown

below, and provide answers as specified below.

a$)$ 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 memoization 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$).$ Write the completed memoization table, where each array entry should

show the shortest path length and the immediate successor node $($e$.$g$.,"8/$e$").$

b$)$ For each node $v$ in the graph, backtrack in the memoization table $($filled in the previous

exercise$)$ from the last entry of the node $($i$.$e$.,M[n,v])$ and write the shortest path and its path

length. Write your answer in the following format: "Shortest path from $x$ to $d$ : $x-y-z-d$

$($path length $=8)",$ where xin$\{a,b,c,e\}.$ Note that path length is the sum of the weights of

edges in the path.