sroutex.gms : Shortest Route Algorithm

Description

```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.
```

Small Model of Type : GAMS

Category : GAMS Model library

Main file : sroutex.gms

``````\$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.

Keywords: shortest route, graph theory
\$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                            /;

Parameter f(i,j) 'shortest route between two cities';

option a:0, f:0;

Scalar
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;
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170