1. Shortest Paths using LP: (5 points) Shortest paths can be cast as an LP using
ID: 3842514 • Letter: 1
Question
1. Shortest Paths using LP: (5 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(u,v) for all (u,v)ÎE
We can compute the single-source by changing the objective function to
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.
1. Shortest Paths using LP: (5 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 dv du S w(u,v for all (u, v EE We can compute the single-source by changing the objective function to max vev. dv Use near 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 Cin the graph below b) Find the distances of the shortest paths from G to all other vertices 10 10 25Explanation / Answer
the shortest path from g to c is via GHBC ashte cost of the vertices is min here and hence if we follow the path we get the min cost that is 16
G to A is 7
G to B is 12
G to C is 16
G to D is 2
G to E is 11
G to F is 17
G to H is 3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.