Problem Detail: I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ and $wcolon Eto 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)$?
Asked By : Lee
Answered By : user1742364
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/53040 Ask a Question Download Related Notes/Documents
