How to formulate LP for shortest path problems?

Question

I'm trying to understand how the LP formulation for shortest path problem works. However I'm having trouble understanding constraints. Why does this formulation work?

http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf

I'm having trouble understanding how the constraints work at pages 15 and 17. I got the main idea and I understand how and why x should take some values but I did not understand how the whole system works in terms of math. Can someone explain? In the exam, I am supposed to be able to create and modify such constraints but I am pretty far from doing that.

Answer 1

What isn't very clear on those slides (pp. 15 and 17) is that the line beginning with "s.t." is actually specifying one constraint per vertex i, i.e., n separate constraints in total (if there are n vertices). Normally this would be communicated by writing something like "∀i ϵ V" alongside the constraint.

In any case, this line says that for each vertex i, the total amount of flow entering it from any other vertices must equal the total amount of flow leaving it -- unless the vertex is the source, in which case the total amount of flow leaving it must be greater by 1, or the sink, in which case the total amount of flow entering it must be greater by 1. It may not be obvious how to come up with this system of constraints in the first place, but by looking at some examples you should be able to see that any shortest path (or in fact, any path from s to t at all) satisfies all of them: every internal vertex in the path will have 1 incoming edge and 1 outgoing edge, while s and t will have just 1 outgoing, or 1 incoming, edge, respectively. Vertices that don't participate in the path at all have 0 incoming and 0 outgoing flow, so they work too.

One more point is that with flow problems, very often the numbers labelling the edges represent capacity constraints -- maximum limits on the amount of flow between the two endpoints -- not costs as they do here.