10.5 Figure 1: Shortest path problem Consider a shortest path problem as shown in figure 11 The destination is node T. The links are undirected, the cost are equal in both directions and are shown along the connecting line segments. For example, gk (1,(1,4)) = 9k (4. (4,1)) = 6. We want to find a shortest path from each i to node T, i.e., a sequence of moves that minimizes total cost to get to destination T from each of the nodes 1, ..., 4. We formulate the problem as one where we require exactly N = 4 moves(stages) to reach the destination but allow degenerate moves from a node i to itself with cost gki, (i, i)) = 0. For N = 4, we have Ji (T) = 0, and for node i = 1,...,4, k = 0...., N -1, Ji (i) = optimal cost of getting from i to T in N - k moves. (1)Formulate this problem into a DP problem ,write down the Bellman Equation and calculate value Ji (i) for i = 1,..., N, k = 0, ...,N-1, where N = 4 in this problem. (2)Based on the results from (1), show the shortest paths from each note to the destination T. 10.5 Figure 1: Shortest path problem Consider a shortest path problem as shown in figure 11 The destination is node T. The links are undirected, the cost are equal in both directions and are shown along the connecting line segments. For example, gk (1,(1,4)) = 9k (4. (4,1)) = 6. We want to find a shortest path from each i to node T, i.e., a sequence of moves that minimizes total cost to get to destination T from each of the nodes 1, ..., 4. We formulate the problem as one where we require exactly N = 4 moves(stages) to reach the destination but allow degenerate moves from a node i to itself with cost gki, (i, i)) = 0. For N = 4, we have Ji (T) = 0, and for node i = 1,...,4, k = 0...., N -1, Ji (i) = optimal cost of getting from i to T in N - k moves. (1)Formulate this problem into a DP problem ,write down the Bellman Equation and calculate value Ji (i) for i = 1,..., N, k = 0, ...,N-1, where N = 4 in this problem. (2)Based on the results from (1), show the shortest paths from each note to the destination T