'**********************************************************
'*                  DANTZIG'S  MODEL                      *
'*                                                        *
'* LIST OF MAIN VARIABLES:                                *
'*                                                        *
'*   NR       : TOTAL NUMBER OF MARKS                     *
'*   V(NR,NR) : PATH VALUES                               *
'*   XL(NR)   : USED FOR WEIGHTING OF EACH PATH           *
'*   IE(NR*2) : SET OF ADOPTED MARKS                      *
'*   V        : PATH VALUE                                *
'*   IR       : NUMBER OF MARKS COMING FROM A SAME MARK   *
'*   RA       : INDEX OF AN ARRIVAL MARK                  *
'*   R$       : = "YES" ON OPTIMAL ROUTE                  *
'*   XM1,XM2  : USED TO SEEK MINIMUM, MAXIMUM PATH        *
'*   IASSO    : ARRIVAL MARK ASSOCIATED WITH SET IE       *
'* ------------------------------------------------------ *
'* PROBLEM DESCRIPTION:                                   *
'* A mountaineer wants to climb up a stiff face. He has   *
'* preliminarily estimated that he can follow different   *
'* paths from 0 (bottom) to 8 (summit) with different     *
'* lengths:                                               *
'*              Path 1:  0 - 1 - 4 - 7 - 8                *
'*              Path 2:  0 - 3 - 5 - 8                    *
'*              Path 3:  0 - 2 - 6 - 5 - 8                *
'*              Path 3a: 0 - 2 - 6 - 7 - 8                *
'*              Path 4:  0 - 1 - 2 - 4 - 7 - 8            *
'*              Path 4a: 0 - 1 - 2 - 4 - 6 - 7 - 8        *
'* The mountaineer wants to know the maximum length rope  *
'* to take,  knowing the following distance matrix        *
'* (meters):                                              *
'*     START/ARR/DIST  START/ARR/DIST  START/ARR/DIST     *
'*       0    1   5      0    2   11     0    3   10      *
'*       1    2   4      1    4   6                       *
'*       2    4   5      2    6   9                       *
'*       3    5   2      4    7   5                       *
'*       5    6   4      5    8   15                      *                                                
'*       6    7   6      7    8   8                       *
'* ------------------------------------------------------ *
'* SAMPLE RUN:                                            *
'*                                                        *
'* DO YOU WANT THE MINIMUM PATH ? NO                      *
'*                                                        *
'* NUMBER OF MARKS ? 9                                    *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #0 ? 3                        *
'* ARRIVAL MARK, VALUE ? 1,5                              *
'* ARRIVAL MARK, VALUE ? 2,11                             *
'* ARRIVAL MARK, VALUE ? 3,10                             *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #1 ? 2                        *
'* ARRIVAL MARK, VALUE ? 2,4                              *
'* ARRIVAL MARK, VALUE ? 4,6                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #2 ? 2                        *
'* ARRIVAL MARK, VALUE ? 4,5                              *
'* ARRIVAL MARK, VALUE ? 6,9                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #3 ? 1                        *
'* ARRIVAL MARK, VALUE ? 5,2                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #4 ? 1                        *
'* ARRIVAL MARK, VALUE ? 7,5                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #5 ? 2                        *
'* ARRIVAL MARK, VALUE ? 6,4                              *
'* ARRIVAL MARK, VALUE ? 8,15                             *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #6 ? 1                        *
'* ARRIVAL MARK, VALUE ? 7,6                              *
'*                                                        *
'* NUMBER OF ARCS FROM MARK #7 ? 1                        *
'* ARRIVAL MARK, VALUE ? 8,8                              *
'*                                                        *
'* RESULTS:                                               *
'*                                                        *
'* THE MAXIMUM VALUE PATH IS:                             *
'*                                                        *
'*     <- 0 - 2 - 6 - 7 - 8 ->                            *
'*                                                        *
'* PATH VALUE =  34                                       *
'*                                                        *
'* ------------------------------------------------------ *
'* REFERENCE:                                             *
'*  Modèles pratiques de décision Tome 2, By Jean-Pierre  *
'*  Blanger, PSI Editions, France, 1982.                  *
'**********************************************************
'PROGRAM DANTZIG
OPTION BASE 0
DEFINT I-N
  CLS
  GOSUB 2000  'INPUT DATA
  GOSUB 3000  'DANTZIG MODEL
  GOSUB 4000  'EDIT OPTIMAL PATH
END

2000 'INPUT DATA
     PRINT
     INPUT " DO YOU WANT THE MINIMUM PATH ? ", R$
     R$ = MID$(R$, 1, 1)
     PRINT
     INPUT " NUMBER OF MARKS ? ", NR
     PRINT
     DIM V(NR, NR), XL(NR), IE(NR * 2)
     FOR I = 0 TO NR - 2
       PRINT " NUMBER OF ARCS FROM MARK #"; I; " ? ";
       INPUT "", IR
       FOR J = 1 TO IR
         INPUT " ARRIVAL MARK, VALUE ? "; RA, V
         V(I, RA) = V
       NEXT J
       PRINT
     NEXT I
     PRINT
     PRINT " RESULTS"
     PRINT
     IF R$ = "O" OR R$ = "o" THEN
       PRINT " THE MINIMUM VALUE PATH IS:"
     ELSE
       PRINT " THE MAXIMUM VALUE PATH IS:"
     END IF
     PRINT
RETURN

3000 'DANTZIG
     XL(0) = 0
     K = 1: IE(K) = 0
3030 IF R$ = "N" THEN
       XM1 = -999999: XM2 = -999999
     ELSE
       XM1 = 999999: XM2 = 999999
     END IF
     FOR IO = 1 TO K
       FOR ID = 1 TO NR
         IF R$ = "N" THEN
           IF V(IE(IO), ID) < XM1 OR V(IE(IO), ID) = 0 THEN GOTO 3170
         ELSE
           IF V(IE(IO), ID) > XM1 OR V(IE(IO), ID) = 0 THEN GOTO 3170
         END IF
         FOR J = 1 TO K
           IF IE(J) = ID THEN F = 1: J = K
         NEXT J
         IF F = 1 THEN F = 0: GOTO 3170
         XM1 = V(IE(IO), ID): IASSO = ID
3170   NEXT ID
       V = XL(IE(IO)) + XM1
       IF R$ = "N" THEN
         IF V > XM2 THEN XM2 = V: IE(K + 1) = IASSO
       ELSE
         IF V < XM2 THEN XM2 = V: IE(K + 1) = IASSO
       END IF
     NEXT IO
     XL(IE(K + 1)) = XM2
     K = K + 1: IF IE(K) <> NR - 1 THEN GOTO 3030
RETURN

4000 'EDIT OPTIMAL PATH
     IO = IE(1): ID = IE(2): K = 1: XL = 0
     PRINT " <- 0 -";
4030 IF V(IO, ID) <> 0 THEN
       XL = XL + V(IO, ID)
       PRINT ID; "-"; : IO = ID: K = K + 1: ID = IE(K)
       GOTO 4050
     END IF
     K = K + 1: ID = IE(K)
4050 IF ID <> NR - 1 THEN GOTO 4030
     XL = XL + V(IO, ID)
     PRINT ID; " ->"
     PRINT
     PRINT " PATH VALUE = "; XL
     PRINT
RETURN

'end of file dantzig.bas