Formalization of the shortest path algorithm to a linear program

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 $\sum\limits_{e\in E }c_ex_e$, subject to $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in 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 $\sum\limits_{e\in B(v)}x_e-\sum\limits_{e\in 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 $i\in 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_{e\in 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}^{n\times n}$ that conserve the flow at each vertex and minimize your objective function $\sum_{e\in 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_{e\in 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.