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$

1 Answer 1

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$
2
  • $\begingroup$ I think the question needs to find the shortest path (route) to visit all nodes and visit all nodes at least once. The formulation you provided calculates a different issue. it creates a connected graph covering all nodes (like MST) $\endgroup$ Jul 28 at 7:45
  • $\begingroup$ @Optimizationteam I think my interpretation of the question is correct, and the OP accepted my answer. For your related question, I added an answer just now: or.stackexchange.com/questions/10762/… $\endgroup$
    – RobPratt
    Jul 28 at 12:56

Your Answer

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

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