TransWikia.com

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

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP