Question 4 (10 marks) To prepare for the increased demand in the coming shopping season. A shoe factory in city o wants to send shoes to a warehouse in city . The shoes can be directly delivered from city 0 to the warehouses in four cities (1, 2, 3, 4), and the warehouse in city 9 can receive shoes from the other four cities (5, 6, 7, 8). The connection among cities is summarized as below: 1 (0,1,46 0 2 (0,2,34) 0 3 4 (0,3,45) (0,4,45) 0 0 9 0 City 0 1 2 3 4 5 5 0 (1,5,46)* 0 (3,5,45) 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 (2,6,38) (3,6,45) 0 0 0 0 0 7 8 0 0 0 (1,8,50) 0 (2,8,50) (3,7,45) (3,8,50) 0 (4,8,50) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 7 0 0 0 0 0 0 0 0 (5,9,39) (6,9,38) (7,9,42) (8,9,50) 0 0 8 0 0 0 0 0 0 (a,b,c) represents there is a connection from a to b, and b can receive shoes from a. The distance from a to b is c; 0 represents there is no connections. (a) Draw the directed graph and show the distance above each edge. (5 marks) (b) Use dynamic programming method to identify the shortest path and the shortest distance from city 0 to city 9