Page 1 of 1

shortest path

Posted: Thu Aug 30, 2018 7:36 pm
by Ilen
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?

Re: shortest path

Posted: Fri Aug 31, 2018 6:40 am
by bussieck
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:

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;
-Michael

Re: shortest path

Posted: Fri Aug 31, 2018 7:52 am
by Ilen
Hi Michael
Thanks a lot

Re: shortest path

Posted: Fri Nov 16, 2018 3:27 pm
by azyrz
Hi ,
I need find shortest paths in a multi model network , and I want to code fifo constraint,
please help me how can I write it in gams?