CODEWITHSUNDEEP
shortest-pathlinear-programming
Felix Ha
Felix Ha

Reputation: 411

Shortest path linear programming

i am stuck at the point maximize d_t at page 4 https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/26-lp.pdf. I absolutely cannot follow the author argument

These relaxation constraints imply that in any feasible solution, d_v is atmost the shortest path distance from s to v .Thus, somewhat counterintuitively,we are correctly maximizing the objective function to compute the shortest path!

We are looking for the shortest path but why do we loogking for max d_t?

Upvotes: 1

Views: 4530

Answers (1)

mattmilten
mattmilten

Reputation: 6726

Imagine the trivial case of the shortest path between two directly connected vertices s and t without any other edges or vertices. Here the LP boils down to this:

maximize   d_t
subject to d_s = 0
           d_t − d_s ≤ l_st for every edge s -> t

The only way to maximize d_t is to set it to the shortest path from s to t - in this case the edge between the two. This is because the second constraint d_t ≤ l_st prohibits any larger value, i.e. any longer path from s to t.

Now, this idea can be transferred to the general case where s and t are not neighbouring vertices: Think of the d variables as shortest paths to all the neighbouring vertices of t. Then the contraints concerned with d_t determine which of these edges must be chosen to define the overall shortest path. It will be satisfied with equality while any higher value for d_t will violate at least one of these contraints.

Upvotes: 2

Related Questions