This week$$s homework is related to the dynamic programming approach to the Traveling Salesperson Problem $($TSP$).$ There are only two problems, but they are more complicated than usual.

Problem $1.$ Consider the following adjacency matrix W for some weighted, directed graph G$.$

Look at the picture attached in the question

Draw a $2$D array D and fill it with the appropriate values. Remember, some of the positions in D make no sense to fill in$,$ so mark these positions with an $$X$.$ In each position of D that does not have an X$,$ write down the cost of the shortest path along with the index j of the vertex vj that gives the minimum. By doing this, you can retrace your steps and determine an optimal tour $($you will need to indicate this tour in Problem $2).$ Note that this $2$D array D will be larger than the one we drew in class.

Be sure to show your work! Along with the $2$D array D$,$ write down any calculations you made to help you compute the values in D$.$

W $1234510813182023078103411010746670115106210$