MINS example: calculating the shortest route

! fill out distance matrix using Floyds algorithm !

File REGSUPP # Supplementary input data File #;

(new) OUTFILE # Output file #;

Set REG # Regions # read elements from file REGSUPP header SDIV;

Coefficient

(all,r,REG)(all,d,REG) ORIG(r,d) # Direct distance from r to d, d>r #;

! initial matrix ORIG has distances for adjacent or near regions

in upper-right triangle only; other entries are zero !

(all,r,REG)(all,d,REG) DISTANCE(r,d) # Shortest distance from r to d #;

(all,r,REG)(all,d,REG) DISTANCE2(r,d) # Possibly shorter distance #;

CHANGES # Count of changes each iteration #;

Read ORIG from file REGSUPP header ADJ;

Formula

(all,r,REG)(all,d,REG) DISTANCE(r,d) = ORIG(r,d);

! fill in lower diagonal !

(all,r,REG)(all,d,REG: ORIG(r,d)< ORIG(d,r)) DISTANCE(r,d)= ORIG(d,r);

! large number means: no direct route !

(all,r,REG)(all,d,REG: DISTANCE(r,d) = 0) DISTANCE(r,d)= 9999999;

(all,r,REG) DISTANCE(r,r) = 5;

Formula

! Calculate shortest route going via third point q !

(all,r,REG)(all,d,REG)

DISTANCE2(r,d) = MINS[q,REG,DISTANCE(r,q)+DISTANCE(q,d)];

! Count improvements !

CHANGES = sum{r,REG, sum{d,REG : DISTANCE2(r,d) < DISTANCE(r,d), 1}};

! update DISTANCE matrix where DISTANCE2 is less !

(all,r,REG)(all,d,REG : DISTANCE2(r,d) < DISTANCE(r,d))

DISTANCE(r,d) = DISTANCE2(r,d);

Write CHANGES to file OUTFILE header CH01;

!**************** loop *************!

Formula

(all,r,REG)(all,d,REG)

DISTANCE2(r,d) = MINS[q,REG,DISTANCE(r,q)+DISTANCE(q,d)];

CHANGES = sum{r,REG, sum{d,REG: DISTANCE2(r,d) < DISTANCE(r,d),1}};

(all,r,REG)(all,d,REG : DISTANCE2(r,d) < DISTANCE(r,d))

DISTANCE(r,d) = DISTANCE2(r,d);

Write CHANGES to file OUTFILE header CH02;

!**************** loop *************!

Formula

(all,r,REG)(all,d,REG)

DISTANCE2(r,d) = MINS[q,REG,DISTANCE(r,q)+DISTANCE(q,d)];

CHANGES = sum{r,REG, sum{d,REG: DISTANCE2(r,d) < DISTANCE(r,d),1}};

(all,r,REG)(all,d,REG : DISTANCE2(r,d) < DISTANCE(r,d))

DISTANCE(r,d) = DISTANCE2(r,d);

Write CHANGES to file OUTFILE header CH03;

!**************** loop *************!

Formula

(all,r,REG)(all,d,REG)

DISTANCE2(r,d) = MINS[q,REG,DISTANCE(r,q)+DISTANCE(q,d)];

CHANGES = sum{r,REG, sum{d,REG: DISTANCE2(r,d) < DISTANCE(r,d),1}};

(all,r,REG)(all,d,REG : DISTANCE2(r,d) < DISTANCE(r,d))

DISTANCE(r,d) = DISTANCE2(r,d);

Write CHANGES to file OUTFILE header CH04;

! when CHANGES = 0, enough loops have been done !

Write

DISTANCE to file OUTFILE header DIST;

URL of this topic: www.copsmodels.com/webhelp/tabmate/hc_minsexample.htm

Link to full GEMPACK Manual

Link to GEMPACK homepage