0
$\begingroup$

This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination.

The idea behind this model is that we assign a flow of 1 for the source and -1 for the destination and every other node has a flow of 0 because they're acting as transfer only.

However, I want to find the shortest path for every node in the graph from the source. It's similar to what the Dijkstra algorithm does however I want to use linear programming.

How can I adapt the model to give me the shortest path for every node in the graph from the source? Here's how the original model I used looks like.

[![graph][1]][1]

Where x12 is the arc from edge 1 to edge 2.

The basic idea would be to have all edges with a flow of -1 however when I try this it doesn't work. Any help would be appreciated. the graph used : [1]: https://i.stack.imgur.com/x8yuT.png

$\endgroup$
5
$\begingroup$

Dijkstra's algorithm finds a shortest path from $s$ to all other nodes in $N \setminus\{s\}$. The corresponding linear programming problem is to minimize $$\sum_{(i,j)\in A} c_{i,j} x_{i,j}$$ subject to $$\sum_{(i,j)\in A} x_{i,j} - \sum_{(j,i)\in A} x_{j,i} = \begin{cases} n-1 &\text{for $i=s$}\\ -1 &\text{for $i\in N \setminus \{s\}$} \end{cases}$$ and $x_{i,j}\ge 0$ for all $(i,j)\in A$.

That is, node $s$ has a supply of $n-1$, and every other node has a demand of $1$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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