! 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;
 ! 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;
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