0
$\begingroup$

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest s-t-path.

By regarding this problem as a special flow network, we can express this using linear programming as follows :

Minimize the function: $$ \sum_{e\in E} c_e\cdot x_e $$

Under the constraints: $$ \forall v\in V-\{s,t\}: \sum_{e\in in(v)}x_e -\sum_{e\in out(v)} x_e = 0 \\ \sum_{e\in out(s)} x_e = 1 \\ \sum_{e\in in(t)} x_e = 1 \\ \sum_{e\in in(s)} x_e = 0 \\ \sum_{e\in out(t)} x_e = 0 \\ \forall e\in E: x_e \ge 0 $$

Here $c_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

About the correctness:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$ is an $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality: $$1\cdot p_{min} \le \sum_{p\in M} \lambda_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda_p \ge 0 , \sum_{p\in M} \lambda_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.

My question now is: Did I miss something in the proof?


Addendum:

It turns out that the above proof needs that each $s-t$-path has a unique cost. Otherwise, there might be no single $s-t$-path with minimal costs. In this case, it can't be shown that the solution $S$ only contains a single of those paths with minimal costs.
However, in this case, by the reasoning above, it still is true that every path in $S$ is optimal. So in this case, we can just pick any path in $S$ as solution (which we can find using e.g. DFS)

Some final (off-topic) remarks:
This whole procedure seems like a lot for a less efficient method to obtain a shortest path. What caught my eye were the following two properties of this algorithm:
$(i)$ Besides the non-negativity constraint, all constraints are actually equalities.
$(ii)$ The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

$\endgroup$
  • $\begingroup$ I've seen that proof-verification is actually off-topic on this site. However, I have follow-up questions that rely on the correctness of this algorithm, and since the proof (at least to me) feels non-trivial, I felt including all this into the follow-up question would make it a too long and composite question. $\endgroup$ – Sudix Apr 3 at 17:38
1
$\begingroup$

There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem.
Your objective function minimizes the cost of the path. The next 5 constraints are the classic flow constraints, which ensure a path between $s$ and $t$. The last constraint is just the bound of variable $x$.

Now, we can start answering your questions:


Given that every s−t-path fulfills the constraints, we can conclude that if S is an s−t-path, then it is an s−t-path with minimal costs.

Correct. It is the shortest path on the defined graph.


Further, S can't contain any cycle with positive weight, as we could simply remove this cycle from S and end up with a lower-cost solution that fulfills the constraints.

The solution of a shortest path problem does not contain a cycle, for obvious reasons.


Did I miss something in the proof?

Sorry, but your proof does not show anything. You are showing that the shortest path is the shortest path.


This whole procedure seems like a lot for a less efficient method to obtain a shortest path

Because you are solving the shortest path problem :)
However, I still recommend you to stick with Dijkstra's algorithm, which is faster than linear programming.


Besides the non-negativity constraint, all constraints are actually equalities.

Yes, good observation. You just have the classic flow constraints (which are all equalities). I recommend you to read the Ahuja's book on network flows (is the best I know, by the way).


The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

You can do that. However, this constraint lies in enumerating all the cycles of your graph, which cannot be fastly solved.

$\endgroup$
  • $\begingroup$ If I solve the linear program with the methods of linear programming, it might happen that the $x_e$ aren't integer. If that happens, I don't really have a path. So, first I formulated the problem as linear programming problem. Then (oh, here I've got the first problem), assuming that $t$ is reachable from $s$ (I'll edit that in), I show that any path is a fesable possible sollution. Then I show that only paths are possible solutions. $\endgroup$ – Sudix Apr 3 at 18:46
  • 1
    $\begingroup$ The resulting matrix of your formulation is unimodular. Furthermore, the optimal solution for your linear problem will always give integer variables. You can look at any textbooks for this proof. $\endgroup$ – Iago Carvalho Apr 3 at 19:45
  • $\begingroup$ Yes, I've read that netflows result in totally unimodular matrices if formulated as linear programs. For the cases however where proving the total unimodularity however isn't possible, a manual reasoning is necessary. Since I have never done this before, having somebody check it over and tell whether that covers all edges felt like a good idea. $\endgroup$ – Sudix Apr 4 at 14:39
  • $\begingroup$ The linear program shouldn't need any enumeration of negative cycles as far as I can see. If we add to the above linear program a constraint $$\sum_{e\in E} x_e \le c$$ and solve the problem for $c= 0, ...,\infty$, at some point the linear program first returns a solution, which then can't contain a cycle. Furthermore, at $c\to \infty$ the solution should only use the best negative cycle (i.e. the one with lowest weight, and if two those cycles exist, the closest one) $\endgroup$ – Sudix Apr 4 at 14:42
  • $\begingroup$ If you do that, you will need to solve $|E|$ linear problems, since you need to vary $c$ in the integer interval $[0, |E|]. However, it does not guarantee that you will have the shortest path associated with your instance. Have a look at imgur.com/5ttz2qm. Assume that there is a great number of nodes within node $\ldots$. As larger will be your $c$, then smaller will be the cost of your shortest path. $\endgroup$ – Iago Carvalho Apr 4 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.