/********************************************************** '* 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 (Y/N) ? N * '* * '* 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.000000 * '* * '* THE MINIMUM VALUE PATH IS: * '* * '* <- 0 - 1 - 2 - 4 - 7 - 8 -> * '* * '* Path Value = 27.000000 * '* ------------------------------------------------------ * '* REFERENCE: * '* Modèles pratiques de décision Tome 2, By Jean-Pierre * '* Blanger, PSI Editions, France, 1982. * '* * '* C++ Release 2.0 By J-P Moreau, Paris. * * (www.jpmoreau.fr) * '*********************************************************/ //PROGRAM DANTZIG; #include #include #define NMAX 25 int NR; double V[NMAX][NMAX]; double XL[NMAX]; int IE[NMAX]; double XM1,XM2,XV; void Data0() { //INPUT DATA int I,J; for (I=0; I XM2) {XM2 = XV; IE[K + 1] = IASSO;} } XL[IE[K + 1]] = XM2; K++; if (IE[K] != NR - 1) goto e30; } //Seek minimum value path void TDantzig1() { //Labels: e30, e50, e70 int F,IASSO,IO,ID,J,K; XL[0] = 0; K = 1; IE[K] = 0; F=0; e30: XM1 = 999999.0; XM2 = 999999.0; for (IO=1; IO<=K; IO++) { for (ID=1; ID<=NR; ID++) { if (V[IE[IO]][ID] > XM1 || V[IE[IO]][ID] == 0) goto e70; for (J=1; J<=K; J++) { if (IE[J] == ID) { F = 1; goto e50; } } e50: if (F == 1) {F = 0; goto e70;} XM1 = V[IE[IO]][ID]; IASSO = ID; e70: ;} XV = XL[IE[IO]] + XM1; if (XV < XM2) {XM2 = XV; IE[K + 1] = IASSO;} } XL[IE[K + 1]] = XM2; K++; if (IE[K] != NR - 1) goto e30; } void Results() { //EDIT OPTIMAL PATH //Labels: e30, e50 int IO,ID,K; double L; IO = IE[1]; ID = IE[2]; K = 1; L=0; printf(" <- 0 - "); e30:if (V[IO][ID] != 0) { L += V[IO][ID]; printf("%d - ", ID); IO = ID; K++; ID = IE[K]; goto e50; } K++; ID = IE[K]; e50:if (ID != NR - 1) goto e30; L += V[IO][ID]; printf("%d ->\n\n", ID); printf(" Path Value = %f\n\n", L); } void Pause() { char answer[2]; printf(" Any key + to exit... "); scanf("%s", answer); } void main() { Data0(); //INPUT DATA TDantzig0(); //DANTZIG MODEL (MAX VALUE PATH) Results(); //EDIT OPTIMAL PATH Data1(); //INPUT DATA TDantzig1(); //DANTZIG MODEL (MIN VALUE PATH) Results(); //EDIT OPTIMAL PATH Pause(); } // end of file dantzig.cpp