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;