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?