Please Read: This must be done with linear programming. It clearly states below that you must include code. You may solve the problems using your choice of software, state which software package/language(s) you used and provide the code or spreadsheet.

1. Shortest Paths using LP: (7 points) Shortest paths can be cast as an LP using distances dv from the source s to a particular vertex v as variables. We can compute the shortest path from s to t in a weighted directed graph by solving. max dt subject to ds 0 dv - du w(ux) for all (uWeE We can compute the single-source by changing the objective function to max Evev dv Use linear programming to answer the questions below. Submit a copy of the LP code and output a) Find the distance of the shortest path from G to C in the graph below. b) Find the distances of the shortest paths from G to all other vertices. A 10 4 18 10 9//25