/
MINPATH-H600001.for
217 lines (217 loc) · 17.2 KB
/
MINPATH-H600001.for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
FILE 5 = LINKIN, UNIT=READER 00000100
FILE 6 = LINKOUT, UNIT = PRINTER 00000200
C 00000300
C MINIMUM PATH ALGORITHM DEVELOPED BY LEON MILLER AND JOHN KIESER AT 00000400
C INTERNATIONAL BANK FOR RECONSTRUCTION AND DEVELOPMENT. WASHINGTON D.C.00000500
C APRIL 1969. 00000600
C THE MINIMUM PATH PROGRAM IN FORTRAN IV HAS BEEN DESIGNED WITH 00000700
C SEVERAL OPTIONS FOR THE USER. IT IS POSSIBLE TO COMPUTE MINIMUM PATHS00000800
C FOR ALL NODES IN A TRANSPORT NETWORK OR ONLY FOR SELECTED NODES. THE 00000900
C USER CAN SPECIFY THE PRINTING OF THE LINK (COST/DISTANCE) ARRAY WHICH00001000
C IS THE INPUT TO THE PROGRAM. HE CAN ALSO INDICATE WHETHER OR NOT THE 00001100
C NODE TO NODE ROUTES SHOULD BE CALCULATED AND PRINTED. EACH OF THESE 00001200
C OPTIONS WILL AFFECT THE OUTPUT AND THE RUNNING TIME OF THE PROGRAM. 00001300
C PROGRAM EFFICIENCY CAN BE IMPROVED WHEN THE USER REDIMENSIONS THE L 00001400
C (LINK) AND X1 (MINIMUM PATH) ARRAYS ACCORDING TO THE SPECIFICATIONS 00001500
C OF THE PROBLEM. FOR EXAMPLE THE USER WOULD WANT TO REDIMENSION HIS 00001600
C ARRAYS AND RECOMPILE THE PROGRAM IF A NEW NETWORK CONTAINED 50 NODES 00001700
C AND HE HAD BEEN PREVIOUSLY UTILIZING THE PROGRAM FOR A 160 NODE NET- 00001800
C WORK. THIS STEP CAN BE EASILY ACCOMPLISHED BY MODIFYING THE TWO 00001900
C COMMON STATEMENTS. THE MAXIMUM NUMBER OF NODES THE PROGRAM CAN 00002000
C HANDLE ON THE B5500 IS 176. 00002100
C 00002200
C THE INPUT IS ENTERED FOR EACH PROBLEM IN THE FORM OF PUNCHED 00002300
C CARDS. THE FIRST CARD CONTAINS THE LINK ARRAY SIZE BY ROW AND COLUMN,00002400
C THE PROBLEM NUMBER AND INTEGER SWITCHS WHICH INDICATE WHETHER A 00002500
C MINIMUM ROUTE IS TO BE DETERMINED, WHETHER MINIMUM PATHS WILL BE 00002600
C COMPUTED ONLY FOR CERTAIN NODES AND WHETHER THE INPUT, LINK ARRAY, 00002700
C SHOULD BE PRINTED. THE FORMAT OF THIS PARAMETER CARD IS AS FOLLOWS 00002800
C COLUMN 1 - 3 NUMBER OF ROWS - IROW 00002900
C COLUMN 4 - 6 NUMBER OF COLUMNS - ICOL 00003000
C COLUMN 7 - 8 PROBLEM NUMBER - PROB 00003100
C COLUMN 9 MINIMUM ROUTE - KSHORT 00003200
C COLUMN 10 - INDIVIDUAL NODE PROCESSING SWITCH INODE 00003300
C COLUMN 11 - INPUT PRINT SWITCH INPRNT 00003400
C 0 = OFF 1 = ON. 00003500
C 00003600
C THE SECOND INPUT IS A SET OF CARDS CONTAINING THE ELEMENTS OF THE 00003700
C LINK ARRAY. THE INITIAL CARD OF THE SET MUST CONTAIN $MILLER IN 00003800
C COLUMNS 2 - 8. THE NEXT CARD MUST CONTAIN THE NAME OF THE LINK ARRAY,00003900
C L, AN EQUAL SIGN AND ARRAY ELEMENTS. THIS IS THE NAMELIST METHOD OF 00004000
C INPUT. THE ELEMENTS CAN BE ENTERED IN TWO WAYS. AN EXAMPLE OF THE 00004100
C FIRST WOULD BE L = 1.,2.,3., ..... AND AN EXAMPLE OF THE SECOND IS 00004200
C L (1,1) = 1., L(2,1) = 2., L(3,1) = 3. IN THE FIRST WAY THE ELEMENTS00004300
C ARE ENTERED AS A WHOLE ARRAY COLUMN BY COLUMN. IN THE SECOND WAY THE 00004400
C ELEMENTS ARE ENTERED INDIVIDUALLY. NOTE THAT L(3,1) INDICATES THE 00004500
C DISTANCE, TIME, COST, ETC., FROM NODE 3 TO NODE 1. THIS WOULD BE THE 00004600
C PREFERRED METHOD IF THERE WERE MANY ZERO ENTRIES. THE LAST ELEMENT 00004700
C MUST BE FOLLOWED BY A $ SIGN SUCH AS L (3,4) = 5.$ OR .5$. NOTE THAT 00004800
C A COMMA MUST BE PUNCHED BETWEEN EACH ELEMENT, AND EACH ELEMENT MUST 00004900
C BE ENTERED WITH A DECIMAL POINT. SEVERAL PROBLEMS CAN BE RUN AT THE 00005000
C SAME TIME USING THIS TECHNIQUE. A LARGE ARRAY OF LINK COSTS, TRAVEL 00005100
C TIMES OR DISTANCES COULD BE ENTERED INTO THE PROGRAM AND THEN 00005200
C INDIVIDUAL LINKS COULD BE MODIFIED AND THE PROGRAM RERUN AS MANY 00005300
C TIMES AS DESIRED. THE PROGRAM IS DESIGNED TO CHECK FOR ADDITIONAL 00005400
C INPUT AFTER EACH PROBLEM IS SOLVED. THE ORDER OF INPUT IS REPEATED 00005500
C FOR EACH PROBLEM. THE LINK ARRAY ALWAYS REMAINS IN MEMORY UNTIL THE 00005600
C INPUT IS EXHAUSTED. IF THE INPRNT SWITCH IS ON, THE THIRD INPUT CARD 00005700
C SHOULD BE A FORTRAN FORMAT STATEMENT WITH THE LEFT PARENTHESIS IN 00005800
C COLUMN 1 AND THE RIGHT PARENTHESIS PUNCHED BEFORE OR ON COLUMN 60. 00005900
C THIS CARD PROVIDES THE FORMAT FOR PRINTING OUT THE LINK ARRAY. 00006000
C 00006100
C IF THE INODE SWITCH IS ON, THE NEXT CARDS SHOULD CONTAIN THE 00006200
C NUMBERS OF THE NODES FOR WHICH MINIMUM PATHS WILL BE COMPUTED. THESE 00006300
C WOULD APPEAR IN COLUMNS 1 - 3 IN AN I FORMAT. 00006400
C 00006500
C THE OUTPUT OF THE PROGRAM IS A LIST OF MINIMUM PATHS, NODE TO NODE00006600
C ROUTES AND THE LINK ARRAY IN THE COMBINATION SPECIFIED ON THE INPUT 00006700
C PARAMETER CARD. 00006800
C THE FOLLOWING IS A SAMPLE INPUT STREAM FOR THREE PROBLEMS WITH 00006900
C DIFFERENT OPTIONS SPECIFIED. **NOTE** THAT WHEN THE NAMELIST INPUT 00007000
C IS ENTERED AS IN PROBLEM ONE THE L ARRAY MUST BE DIMENSIONED IN 00007100
C COMMON EXACTLY AS THE NUMBER OF ROWS AND COLUMNS INDICATE. THE 00007200
C LINKS ARE SPECIFIED IN TERMS OF DISTANCE FOR THESE PROBLEMS. 00007300
C 9 9 2101 00007400
C$MILLER 00007500
C L= 0.0,4.0,2.0,2.0,0.0,0.0,0.0,0.0,0.0, 00007600
C 4.0,0.0,1.0,0.0,2.0,0.0,3.0,0.0,0.0, 00007700
C 2.0,1.0,0.0,4.0,3.0,0.0,0.0,0.0,0.0, 00007800
C 2.0,0.0,4.0,0.0,0.0,3.0,0.0,0.0,16.0, 00007900
C 0.0,2.0,3.0,0.0,0.0,3.0,1.0,0.0,0.0, 00008000
C 0.0,0.0,0.0,3.0,3.0,0.0,0.0,6.0,0.0, 00008100
C 0.0,3.0,0.0,0.0,1.0,0.0,0.0,6.0,0.0, 00008200
C 0.0,0.0,0.0,0.0,0.0,6.0,6.0,0.0,5.0, 00008300
C 0.0,0.0,0.0,16.0,0.0,0.0,0.0,5.0,0.0$ 00008400
C1H ,9F5.1) 00008500
C 9 9 31 00008600
C$MILLER 00008700
C L(9,8) =13., 00008800
C L(3,1) =10.$ 00008900
C 7 7 411 00009000
C$MILLER 00009100
C L(1,2)=0.$ 00009200
C03 00009300
C05 00009400
C THE FOLLOWING IS A PARTIAL SAMPLE OF OUTPUT 00009500
C 00009600
C MINIMUM PATHS FOR PROBLEM 2 FOR NODE 1 00009700
C FROM NODE 1 TO NODE 9 16.00 00009800
C 00009900
C MINIMUM ROUTES FROM NODE 1 00010000
C *** ROUTE TO NODE 9 00010100
C NODE 8 TO NODE 9 5.00 00010200
C NODE 6 TO NODE 8 6.00 00010300
C NODE 4 TO NODE 6 3.00 00010400
C NODE 1 TO NODE 4 2.00 00010500
C 00010600
C MINIMUM PATH ALGORITHM 00010700
COMMON L(9,9),X1(9) 00010800
REAL L 00010900
NAMELIST /MILLER/ L 00011000
5 READ (5,100,END=1000) IROW,ICOL,PROB,KSHORT,INODE,INPRNT 00011100
100 FORMAT (I3,I3,I2,I1,I1,I1) 00011200
C READ CONTROL CARD IROW = NUMBER OF ROWS 00011300
C ICOL = NUMBER OF COLS 00011400
C PROB = PROBLEM NUMBER 00011500
C KSHORT = SWITCH FOR MINIMUM PATH STEP 0=OFF 00011600
C INODE =SWITCH FOR INDIVIDUAL NODE PROCESSING 00011700
C READ LINK ARRAY IN NAMELIST FORM 00011800
READ (5,MILLER) 00011900
CALL MINPTH (IROW,ICOL,PROB,KSHORT,INODE,INPRNT) 00012000
GO TO 5 00012100
1000 STOP 00012200
END 00012300
SUBROUTINE MINPTH (IROW,ICOL,PROB,KSHORT,INODE,INPRNT) 00012400
COMMON L(9,9),X1(9) 00012500
DIMENSION A(10) 00012600
REAL L 00012700
IF (INPRNT .EQ. 0) GO TO 5 00012800
WRITE (6,900) PROB 00012900
900 FORMAT(1H1,55X,20HMINIMUM PATH PROBLEM,2X,I2) 00013000
WRITE (6,901)IROW,ICOL 00013100
READ (5,902)(A(I),I=1,10) 00013200
901 FORMAT(1H0,10HLINK ARRAY,2X,I3,6H ROWS ,I3,5H COLS) 00013300
902 FORMAT (10A6) 00013400
WRITE (6,A) ((L(I,J),J=1,ICOL),I=1,IROW) 00013500
5 K=0 00013600
10 DO 6 I=1,IROW 00013700
X1(I)= 0 00013800
6 CONTINUE 00013900
C K= NODE TO WHICH PATHS WILL BE COMPUTED 00014000
IF (INODE .EQ. 0) GO TO 7 00014100
READ (5,920,END=1000) K 00014200
920 FORMAT (I3) 00014300
IF (K .EQ. 0) RETURN 00014400
GO TO 8 00014500
7 K=K+1 00014600
IF(K .LE. IROW) GO TO 8 00014700
RETURN 00014800
8 DO 20 J=1,ICOL 00014900
IF(L(K,J) .EQ. 0.0) GO TO 20 00015000
X1(J)=L(K,J) 00015100
20 CONTINUE 00015200
C COMPUTE FIRST ESTIMATE OF DISTANCES FROM K TO ALL NODES 00015300
21 DO 30 J=1,ICOL 00015400
XTEMP=0.0 00015500
IF(J .EQ.K) GO TO 30 00015600
IF (L(K,J) .GT. 0.0) GO TO 30 00015700
IF(X1(J) .GT. 0.0) GO TO 30 00015800
DO 29 I=1,IROW 00015900
IF (L(I,J) .EQ. 0.0) GO TO 29 00016000
IF(X1(I) .EQ. 0.0) GO TO 29 00016100
X1(J)=X1(I) + L(I,J) 00016200
IF (XTEMP .EQ. 0.0) XTEMP = X1(J) 00016300
IF (X1(J) .LT. XTEMP) XTEMP =X1(J) 00016400
29 CONTINUE 00016500
X1(J) =XTEMP 00016600
30 CONTINUE 00016700
DO 35 I=1,IROW 00016800
IF(I .EQ. K) GO TO 35 00016900
IF(X1(I) .EQ. 0.0) GO TO 21 00017000
35 CONTINUE 00017100
C COMPUTE FINAL MINIMUM DISTANCE FROM K TO ALL NODES 00017200
37 ICOUNT =0 00017300
DO 40 J=1,ICOL 00017400
DO 40 I=1,IROW 00017500
IF(L(I,J) .EQ. 0.0) GO TO 40 00017600
IF((X1(J)-X1(I) -L(I,J)).LT. .0001) GO TO 40 00017700
ICOUNT =ICOUNT +1 00017800
X1(J)=L(I,J) +X1(I) 00017900
40 CONTINUE 00018000
IF (ICOUNT .NE. 0) GO TO 37 00018100
WRITE (6,903) PROB,K 00018200
903 FORMAT(1H1,26HMINIMUM PATHS FOR PROBLEM , I2,10H FOR NODE ,I3) 00018300
904 FORMAT(1H ,10HFROM NODE ,I3,1X,8HTO NODE ,I3,5X,F10.2) 00018400
DO 41 I=1,IROW 00018500
WRITE (6,904)K,I,X1(I) 00018600
41 CONTINUE 00018700
IF(KSHORT .EQ. 0 ) GO TO 51 00018800
C FIND MINIMUM ROUTE FROM NODE TO NODE 00018900
WRITE(6,905) K 00019000
905 FORMAT (1H1,37HMINIMUM NODE TO NODE ROUTES FROM NODE, 00019100
12X,I3) 00019200
DO 50 J=1,ICOL 00019300
IF (J .EQ. K) GO TO 50 00019400
MM =0 00019500
WRITE(6,907) J 00019600
907 FORMAT(1H0,17H*** ROUTE TO NODE,1X,I3) 00019700
M=J 00019800
44 DO 45 I=1,IROW 00019900
IF(MM .EQ. I) GO TO 45 00020000
IF (L(I,M) .EQ. 0.0) GO TO 45 00020100
IF ((X1(M) -X1(I)) .LT. 0.0 )GO TO 45 00020200
IF((X1(M)-X1(I) -L(I,M)) .LT. 0.0) GO TO 45 00020300
IF((X1(M)-X1(I) -L(I,M)) .LT. .0001) GO TO 46 00020400
45 CONTINUE 00020500
STOP 00020600
46 WRITE (6,906)I,M,L(I,M) 00020700
906 FORMAT(1H ,5HNODE ,I3,1X,8HTO NODE ,I3,3X,F7.2) 00020800
MM=M 00020900
M=I 00021000
IF (M .EQ. K) GO TO 50 00021100
GO TO 44 00021200
50 CONTINUE 00021300
51 CONTINUE 00021400
GO TO 10 00021500
1000 STOP 00021600
END 00021700