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.

  • $\begingroup$ Is the graph complete ? $\endgroup$
    – AJed
    Nov 17, 2012 at 16:15
  • $\begingroup$ Can you please cite the reference from where you got the question. It seems that you used one. $\endgroup$
    – AJed
    Nov 17, 2012 at 16:22
  • 1
    $\begingroup$ Yes, sure- I'm trying to read "Efficient Shortest Path Simplex Algoriths" by Donald Goldfarb, Jianxiu Hao, and Sheng-Roan Kai $\endgroup$
    – Joni
    Nov 17, 2012 at 16:33
  • $\begingroup$ @Ajed: there should be no need for the graph to be complete for simplex to be able to find shortest paths $\endgroup$ Nov 18, 2012 at 21:47
  • $\begingroup$ @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. $\endgroup$
    – AJed
    Nov 18, 2012 at 23:36

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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