Hi everyone

I need to find shortest paths in a weighted graph with positive edge weights , for some node , not all node .

for example I want to have shortest path from nodes 1,4,7 to all nodes in graph .

I want to implement of Floyd–Warshall algorithm in GAMS , I need some help. Please help me .

Or

Is there a better way to find the shortest path from some nodes to any node in the network?

## shortest path

### Re: shortest path

I don't know about implementing the Floyd–Warshall algorithm in GAMS, that might not be the best language for such an algorithm. But shortest path is a simple LP problem. The dual of the SP is easier because instead of creating an infeasibility if you can't reach a node from the start node it would go unbounded which we can prevent by using a large enough upper bound on the dual variable. If you google sp and lp you will find many good hits that explain this in more detail:

-Michael

Code: Select all

```
set i nodes / 1*5 /; alias (i,j); set a(i,j) edges;
parameter len(i,j) edges / 1.2 4, 1.3 1, 2.4 2, 3.2 2, 5.3 1/
option a<len;
positive variable d(i) distance from start node;
variable obj;
equation
defdualarc(i,j)
defdualobj;
defdualobj.. obj =e= sum(i, d(i));
defdualarc(a(i,j)).. d(j) =l= d(i) + len(a);
model spDual /defdualobj, defdualarc /;
scalar maxdist; maxdist = sum(a, len(a));
d.up(i) = maxdist;
* 1 is start node
d.up('1') = 0;
solve spDual max obj us lp;
set unreachable(i); unreachable(i) = abs(maxdist-d.l(i))<1e-6;
d.l(unreachable) = 0;
display unreachable, d.l;
```