# How can I find the shortest path for all nodes in a graph from a source $s$?

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

## 1 Answer

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$$.

• 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) Jul 28, 2023 at 7:45
• @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/… Jul 28, 2023 at 12:56