shortest path

Archive of Gamsworld Google Group
Post Reply
Ilen
User
User
Posts: 2
Joined: 3 weeks ago

shortest path

Post by Ilen » 3 weeks ago

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?

User avatar
bussieck
Moderator
Moderator
Posts: 147
Joined: 2 years ago

Re: shortest path

Post by bussieck » 3 weeks ago

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

Ilen
User
User
Posts: 2
Joined: 3 weeks ago

Re: shortest path

Post by Ilen » 3 weeks ago

Hi Michael
Thanks a lot

Post Reply