Minimal paths as solution of a linear program of a special network flow
-
05-11-2019 - |
题
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.)
没有正确的解决方案