A road construction project will be initiated to join cities A and $K.$ The road could pass through some intermediate cities B through J$.$ There are costs associated with each possible segment of road between cities, as shown in Fig. $1.$

Figure $1$: Problem $2$

Use dynamic programming to make a table as done in class with the optimal routes from any candidate city to $K.$

What is the optimal route to build the road $($what cities are included and in what order$)$ and what is the total optimum cost?