Linear Programming (LP) - Shortest paths can be cast as an LP using distances dv from the source s to a particular vertex v as variables. If you are using matlab or something like lingo can you please explain how to use it? or show how you inputted into the program?

-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(u,v) for all (u,v)E

-We can compute the single source by changing the objective function to max

Use linear programming to answer the questions below. State the objective function and constraints for each problem and include a copy of the LP code and output. a) Find the distance of the shortest path from vertex 0 to vertex 7 in the graph below. b) Find the distances of the shortest paths from vertex 0 to all other vertices.

2 100 2 7 10 I 4 6 7 I 2 5 10 3 5