Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I saw that I can formulate single-source shortest path as the following linear program:
Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find $\max\,d(s,t)$ such that
\begin{align*} d(s,v) &\le d(s,u)+w(u,v) \quad \forall (u,v)\in E \\ d(s,s) &=0 \end{align*}
We want to find the shortest path from $s$ to $t$ so we are we maximizing $d(s,t)$?
What you have here is a dual formulation of the problem (not the standard one, but an equivalent one). According to strong duality, both the optimal primal and the optimal dual problem have the same objective value (i.e., the shortest path distance from $s$ to $t$). The constraints of the dual problem are then the optimality criteria of the shortest path problem. Note that you can obtain the actual shortest path by finding any $s$-$t$-path in the subgraph that is induced by the edges for which the corresponding dual constraint is tight.
By the way, there is a neat interpretation of this formulation: For each edge $(u,v)$, consider a string with length $w(u,v)$ and tie the ends of these strings together at the corresponding nodes they share. If you put the knot for $s$ and the knot for $t$ as far away from each other as possible, you will end up with several tight strings, which then describe the shortest path.
