MODEL:
 ! Dynamic programming illustration (see Anderson,
   Sweeney & Williams, An Intro to Mgt Science, 
   6th Ed.),  or Hillier & Lieberman, various editions.
   We have a network on a number of states/cities.  We
   want to find the length of the shortest route from
   every state to the final/last state.  As special case,
   this allows us to find the cheapest/shortest path
   from state 1 to the final state.;
 ! Keywords: Dynamic programming, Shortest path, Recursion;
SETS:
 ! Here is our primitive set of ten states, where
   F( i) = the shortest path distance
   from state i to the last state;
  state: F;

 ! The derived set, MOVE, lists the moves that 
   exist between the states (note: not all state
   pairs are directly linked by a road. Moves
   are assumed to be one way.);
  MOVE( state, state): D;
 ! D( i, j) is the distance from city i to j;
ENDSETS

DATA:
  STATE = S1..S10;
 ! Here are roads/moves and distances that correspond to the 
   moves that are available;
  MOVE, D= 
   S1,S2,1  S1,S3,5  S1,S4,2
   S2,S5,13 S2,S6,12 S2,S7,11
   S3,S5,6  S3,S6,10 S3,S7,4
   S4,S5,12 S4,S6,14
   S5,S8,3  S5,S9,9
   S6,S8,6  S6,S9,5
   S7,S8,8  S7,S9,10
   S8,S10,5
   S9,S10,2;
 ! D( i, j) is the distance from city i to j;
ENDDATA

SUBMODEL DYNPROG:
! If you are already in State last state, then the cost to
  travel to City 10 is 0;
 F( STATESN) = 0;

! The following is the classic dynamic programming
  recursion. In words, the shortest distance from
  State i to State 10 is the minimum over all 
  state j reachable from i of the sum of the 
  distance from i to j plus the minimal distance
  from j to City 10;
 @FOR( state( i)| i #LT# STATESN:
  F( i) = @MIN( MOVE( i, j): D( i, j) + F( j))
 );
ENDSUBMODEL


CALC:
 STATESN = @SIZE( STATE); ! Get index number of final state;
 @SOLVE( DYNPROG);  ! Do the Dynamic Programming;

! Write a simple report, showing best decision for each state...;
! Find an optimal decision for all states, except last;
 @WRITE('     Dynamic Programming Solution', @NEWLINE(1));
 @WRITE(' If in this state.      Choose this state next', @NEWLINE(1));
 @FOR( STATE( i) | i #LT# STATESN:
! Find next state for i on shortest route;
   @FOR( MOVE( i,j) | F(i)  #EQ#  D(i,j) + F(j):
     @WRITE( @FORMAT( STATE(i),'14s'),'       ', @FORMAT( STATE(j), '15s'), @NEWLINE(1));
       );
     );

 @WRITE(@NEWLINE(1), "   The Least Cost Path From State 1 is:", @NEWLINE(1));
 NEXT1 = -1;
 START1 = 1;
 @WHILE( NEXT1 #NE# STATESN:
   @FOR( MOVE( i,j) | i #EQ# START1 #AND# F(i)  #EQ#  D(i,j) + F(j):
     NEXT1 = j;
       );
     @WRITE( @FORMAT( STATE(START1),'14s'),'     to', @FORMAT( STATE(NEXT1), '15s'), @NEWLINE(1));
   START1 = NEXT1;
       );
ENDCALC
END