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 .
Is there a better way to find the shortest path from some nodes to any node in the network?
Archive of Gamsworld Google Group
3 posts • Page 1 of 1
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;