Question Detail: I’m trying to understand a formalization of the shortest path algorithm to a linear programming problem: For a graph $G=(E,V)$, we defined $F(v)={e in E mid t(e)=v }$ and $B(v)={ e in E mid h(e)=v}$ where $t(e)$ is a tail of a node, and $h(e)$ is a head of a node. Also the solutions for the conditions for the linear problem was defined as $b_v=1$ for every node $v$ except of the root $r$ which from it we find all the shortest paths in the graph where $b_r=-(n-1)$. It is written here “We associate a flow (primal variable) $x_e$ with each arc $e in E$. The main linear program is to minimize $sumlimits_{ein E }c_ex_e$, subject to $sumlimits_{ein B(v)}x_e-sumlimits_{ein F(v)}x_e=b_v$ for all $v in V$ and $x_e geq 0$ for all $e in E$, where $c_e$ is the length of arc $e$. I’d really love your help with understanding what does $x_e$ represent. Is it the number of times I use $e$ in order to find all the shortest paths in the graph? I don’t understand why does the above condition for this linear program is as at it, why does $sumlimits_{ein B(v)}x_e-sumlimits_{ein F(v)}x_e=b_v$ for all $v in V$ should be $1$ for every node and $-(n-1)$ for the all the root? If I think of a $3$ nodes tree for a graph,for the middle node we get that the condition equals to $1$, which makes me think that I might be misunderstood what $x_e$ stands for.
Asked By : Joni
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6717
Answered By : Marc Khoury
This formalization takes Dijkstra’s algorithm and formalizes it as a network flow problem. In the network flow problem, $b_i$ represents the amount of flow that enters or leaves a network at vertex $iin V$. If $b_i > 0$ we say that $i$ is a source supplying $b_i$ units of flow. If $b_i < 0$ we say that $i$ is a sink with a demand of $|b_i|$ units of flow. Here $B(v)$ are $v$’s outgoing edges and $F(v)$ are $v$’s incoming edges. So the condition $sum_{ein B(v)} x_e – sum_{e in F(v)}x_e = b_v = 1$ means that I’m allowed to supply $1$ more unit of flow coming out of $v$ than going into $v$. Now in the network flow algorithm I’m pushing flow into the sink node, in this case the root $r$. Since each node can supply only $1$ unit of flow, the amount of flow going into $b_r$ is $n-1$. So these equations are satisfied when each node pushes it’s one unit of flow down to the sink node, enforcing that we find the shortest path from every node to $r$. Now you can see that $b_r=-(n-1)$ means that it expects the $1$ unit of flow from every node. From this it should be easy to see that $x_e$ represents the number of times you’ve travelled along the edge $e$ in every shortest path. The minimum cost flow problem asks for flows $x_e in mathbb{R}^{ntimes n}$ that conserve the flow at each vertex and minimize your objective function $sum_{ein E} c_e x_e$. So if $x_e$ is the number of times you’ve used the edge $e$ in all the shortest paths and $c_e$ is the cost of pushing $1$ unit of flow across $e$ (i.e. the length of $e$), then $sum_{ein E} c_e x_e$ is summing the cost of every edge used across all the shortest paths. Let’s take an example with three nodes and a graph that looks like 0–1–2.
Assume that 2 is the root and each edge is unit length. So the shortest path for vertex 0 is 0–1–2 and the shortest path for vertex 1 is 1–2. So I used 0–1 once and 1–2 twice. This satisfies the equations that the units of flow going into a vertex must be one less than those going out. Additionally we have $-2$ units of flow going into vertex $2$, so that equation is satisfied as well. The objective function then sums to $3$ which is our minimum flow cost.
