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

Operations Research Asked by WindBreeze on March 1, 2021

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]]

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 :
: https://i.stack.imgur.com/x8yuT.png

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

Correct answer by RobPratt on March 1, 2021

## Related Questions

### How to optimize a utility function that contains step function?

1  Asked on January 5, 2022

### How to display the range of coefficients in docplex log?

1  Asked on January 1, 2022 by ehsank

### Scenario based approach to value-at-risk optimization using mixed-integer programming

1  Asked on January 1, 2022

### Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa

### How to balance the workload of teachers in OR-Tools (maximization of the minimum)

1  Asked on December 18, 2021 by neverletgo

### How to linearize a quadratic constraint to add it then via a callback function

2  Asked on December 9, 2021 by farouk-hammami

### Decision variable transformation in Gurobi

2  Asked on December 5, 2021

### Possibility of indexing decision variables with 2 indices using a set of tuples in Pyomo

3  Asked on November 24, 2021

### View of Constraints and Decision Variables in Pyomo

1  Asked on November 17, 2021

### CPLEX Python API Manual with References

1  Asked on November 4, 2021

### Are Python and Julia used for optimization in industry?

15  Asked on August 19, 2021

### How to improve the quality of code in OR?

3  Asked on August 19, 2021

### How would you characterize “optimization data?”

4  Asked on August 19, 2021 by marco-lbbecke

### Local optimum of dual of non-linear program

2  Asked on August 19, 2021

### Combinatorial Optimization using AMPL

2  Asked on August 19, 2021 by user3831

### Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen

### Tips on How to Review Operations Research Literature Effectively?

2  Asked on August 19, 2021 by ehsan

### Polynomially solvable cases of zero-one programming

1  Asked on August 19, 2021

### Error evalution for linear fits

1  Asked on August 19, 2021 by jane