Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Is the graph complete ? –  AJed Nov 17 '12 at 16:15
    
Can you please cite the reference from where you got the question. It seems that you used one. –  AJed Nov 17 '12 at 16:22
1  
Yes, sure- I'm trying to read "Efficient Shortest Path Simplex Algoriths" by Donald Goldfarb, Jianxiu Hao, and Sheng-Roan Kai –  Joni Nov 17 '12 at 16:33
    
@Ajed: there should be no need for the graph to be complete for simplex to be able to find shortest paths –  Carlos Linares López Nov 18 '12 at 21:47
    
@CarlosLinaresLópez it was just a question to understand the question in more details. Especially as the differenec between indegree and outdegree must be 1 according to the question. –  AJed Nov 18 '12 at 23:36
show 1 more comment

1 Answer

up vote 1 down vote accepted

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.

example graph

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.