3

We formulate the shortest path problem as follows:

We have a directed graph $D=(V,A)$ with length $c_{j}$ for each arrow $e_j$ in $A$ and two special points $s,t\in V$.
The node-arc incidence matrix $A$ is defined as $a_{ij}$ is $1$ if the arrow $e_j$ leaves from $i$, $-1$ if the arrow $e_j$ arrives in $i$ or $0$ otherwise.
Our decision variable is $f_j$, which is $1$ if the path uses arrow $e_j$.
PRIMAL: We want to minimalize $\sum_{e_j\in A}c_jf_j$ under the conditions that $Af=(1,0,...,0,-1)^\top$ and $f\geq 0$.
DUAL: We want to maximize $\pi_s-\pi_t$ under the conditions that $\pi^\top A\leq c$ and $\pi\in\mathbb{R}^m$.

I have the following three statements:
(i) There exists a shortest s-t walk.
(ii) The dual $LP$ problem has a feasible solution.
(iii) There is no circuit with negative total length.

Unfortunately I have absolutely no idea how to begin to prove the equivalence of these statements.

EDIT: Extra condition: from each vertex there exists at least one directed path to $t$.

  • 1
    I don't see how (i) and (iii) are equivalent. For example, take a graph that has no edges and two points, $s$ and $t$. Then, there is no shortest $s-t$ walk in the graph, since there are no edges to traverse. However, there is also no circuit with negative total length, since there are no circles. – 5xum Oct 21 '15 at 17:11
  • If I remember correctly my courses, I think you'll need the Min-Cut Theorem to prove that. – hlapointe Oct 25 '15 at 18:05
  • @hlapointe I know that theorem, but how would I use it? –  Oct 25 '15 at 18:14
  • 1
    In view of the points made by @5xum , I believe you will need to add the assumption that the graph is irreducible, so that there is a path from every node to every other node. In that case, you can argue equivalence between (i) and (iii) just from basic thought experiments about traversing the graph, while (ii) comes from duality for linear programs. – Michael Oct 26 '15 at 23:08
  • 1
    Your edited "extra condition" is not enough since you can have a graph with a direct link from $s$ to $t$ (being the only path between those two nodes, so there trivially exists a "shortest" path from $s$ to $t$), while the other parts of the graph can have negative cycles as long as all nodes also have direct links to $t$ (so they satisfy your edited condition). – Michael Oct 26 '15 at 23:11

1 Answers1

0

As in the comments above, you will need to make additional assumptions, such as assuming the graph is irreducible (your edited extra condition is not enough). Here is a slightly less restrictive set of assumptions that also work:

Assume:

-For every vertex, there is a directed path from $s$ to that vertex.

-For every vertex, there is a directed path from that vertex to $t$.

-The lengths $c_j$ are real numbers (possibly negative, but certainly finite).

Solution approach to show equivalence between (i) and (iii):

a) Suppose the graph contains a cycle with negative length. Show that for any arbitrarily large positive integer $M$, we can find a walk from $s$ to $t$ with total length less than $-M$.

b) Suppose there are no cycles with negative length. Show that for every walk from $s$ to $t$, we can find another walk from $s$ to $t$ that has total length less than or equal to the first, and that does not repeat any nodes. [Hence, to find a shortest walk, we can restrict attention to walks that have at most $N-1$ hops, where $N$ is the number of graph nodes. That is, we can restrict attention to a finite number of options.]

Community
  • 1
Michael
  • 23,905