sroutex.gms : Shortest Route Algorithm
The problem is to find the shortest route or lowest transport
cost from each city to all others. This example is the same as
sroute except a shortest path algorithm is written using loops.
Reference:
- Dantzig, G B, Chapter 17.3. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.
Small Model of Type: GAMS
<![CDATA[
$Title Shortest Route Algorithm (SROUTEX,SEQ=93)
$Ontext
The problem is to find the shortest route or lowest transport
cost from each city to all others. This example is the same as
sroute except a shortest path algorithm is written using loops.
Dantzig, G B, Chapter 17.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.
$Offtext
Set i cities / boston, chicago, dallas, kansas-cty, losangeles
memphis, portland, salt-lake, wash-dc /
Alias(i,j,k)
Parameter a(i,j) arcs and cost /
boston .chicago 58, kansas-cty .memphis 27
boston .wash-dc 25, kansas-cty .salt-lake 66
chicago .kansas-cty 29, kansas-cty .wash-dc 62
chicago .memphis 32, losangeles .portland 58
chicago .portland 130, losangeles .salt-lake 43
chicago .salt-lake 85, memphis .wash-dc 53
dallas .kansas-cty 29, portland .salt-lake 48
dallas .losangeles 85
dallas .memphis 28
dallas .salt-lake 75 /
Parameters f(i,j) shortest route between two cities;
Option a:0, f:0;
Scalars old old total distance
new new total distance ;
a(i,j) = max(a(i,j),a(j,i));
Display a;
f(i,j) = inf; f(i,i) = 0; f(i,j) $= a(i,j);
Loop(i,
new = na;
repeat(
f(i,j)$(not sameas(i,j)) = smin(k$a(k,j), f(i,k)+ a(k,j));
old=new;
new = sum(j$(f(i,j) < inf), f(i,j));
until old = new ) );
Display f ;
]]></plaintext></body></div>