20 5 2 4 3 5 6 8 8 8 9 14 6 10 7 6 1 14 15 9 9 10 8 14 14 4 6 1 11 8 8 8 8 10 4 7 12 1 9 9 8 8 9 5 1 9 8 13 18 9 9 8 9 14 3 14 2 3 9 10 8 3 16 2 4 8 9 9 2 3 5 10 8 5 4 5 18 1 12 9 9 9 14 14 3 15 14 2 8 8 9 2 3 19 8 20 2 4 7 8 14 2 5 17 9 9 4 10 19 6 2 8 10 9 14 2 10 2 8 14 1 7 8 2 13 20 9 8 2 9 5 9 14 2 14 11 10 20 1 17 8 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 3 20 15 10 5 6 9 0 11 2 0 20 16 8 4 2 1 0 0 INTEGER FLIST(200),DFLIST(200),KF(51),MJ(50),WJ(50),W(50),H(50), PAP00001 + IN,INPUT,OUTP,TEMP(10) PAP00002 C PAP00003 C THIS PROGRAM CALCULATES THE SHORTEST PATH LENGTHS FROM A SPECIFIC PAP00004 C NODE (J0) TO ALL OTHER NODES IN A NETWORK AND THE SHORTEST PATHS PAP00005 C BETWEEN THIS NODE (J0) AND OTHER NODES (KE). PAP00006 C PAP00007 C FLIST(NUMBER OF EDGES) PAP00008 C DFLIST(NUMBER OF EDGES) PAP00009 C KF(NUMBER OF NODES+1) PAP00010 C PAP00011 C FLIST, DFLIST, AND KF REPRESENT THE NETWORK PAP00012 C PAP00013 C MJ(NUMBER OF NODES) PAP00014 C WJ(NUMBER OF NODES) PAP00015 C W(NUMBER OF NODES) PAP00016 C H(NUMBER OF NODES) PAP00017 C PAP00018 DATA INF,IN,INPUT,OUTP /1000000,4,5,6/ PAP00019 C PAP00020 C IN CHANNEL FOR INPUT J0 PAP00021 C INPUT CHANNEL FOR INPUT NETWORK PAP00022 C OUTP CHANNEL FOR OUTPUT PAP00023 C PAP00024 C INPUT OF THE NUMBER OF NODES N PAP00025 C PAP00026 1 READ(INPUT,100) N PAP00027 K=0 PAP00028 KF(1)=0 PAP00029 C PAP00030 C INPUT OF THE NETWORK PAP00031 C PAP00032 DO 4 I=1,N PAP00033 READ(INPUT,100) IT,(TEMP(J),J=1,IT) PAP00034 IF (IT.EQ.0) GO TO 3 PAP00035 JA=K+1 PAP00036 JB=K+IT PAP00037 JJ=1 PAP00038 DO 2 J=JA,JB PAP00039 FLIST(J)=TEMP(JJ) PAP00040 2 JJ=JJ+1 PAP00041 C PAP00042 READ(INPUT,100) IDUMMY,(DFLIST(J),J=JA,JB) PAP00043 K=K+IT PAP00044 3 KF(I+1)=K PAP00045 4 CONTINUE PAP00046 C PAP00047 C INPUT OF START NODE J0 PAP00048 C PAP00049 5 READ(IN,101) J0 PAP00050 IF (J0.LE.0) STOP PAP00051 C PAP00052 CALL SHPTHL(FLIST,DFLIST,KF,N,MJ,J0,WJ) PAP00053 C PAP00054 WRITE(OUTP,200) J0 PAP00055 IF (N.GT.0) WRITE(OUTP,201) (I,MJ(I),I=1,N) PAP00056 C PAP00057 C INPUT OF END NODE KE PAP00058 C PAP00059 6 READ(IN,101) KE PAP00060 IF (KE.LE.0) GO TO 5 PAP00061 C PAP00062 CALL SHPATH(J0,KE,WJ,H,NI,W) PAP00063 C PAP00064 WRITE(OUTP,202) J0,KE,MJ(KE) PAP00065 WRITE(OUTP,203) (W(I),I=1,NI) PAP00066 GO TO 6 PAP00067 C PAP00068 100 FORMAT(10I8) PAP00069 101 FORMAT(I4) PAP00070 200 FORMAT(21H1DISTANCES FROM NODE ,I5/) PAP00071 201 FORMAT(10(I7,1H-,I4)) PAP00072 202 FORMAT(//15H PATH FROM NODE,I7,9H TO NODE ,I7,13H (PATHLENGTH=, PAP00073 + I7,1H)) PAP00074 203 FORMAT(1H ,20I6) PAP00075 END PAP00076 SUBROUTINE SHPTHL(FLIST,DFLIST,KF,N,MJ,J0,WJ) SPL00001 INTEGER FLIST(200),DFLIST(200),KF(51),MJ(50),NJ(50),WJ(50) DATA INF /1000000/ C C SHPTHL CALCULATES THE SHORTEST PATH LENGTHS (MJ) FROM A SPECIFIC C NODE (J0) TO ALL OTHER (N-1) NODES IN A NETWORK (FLIST,DFLIST,KF). C PREDECESSOR NODES ARE STORED IN WJ. C C FLIST : FORWARD INDEX LIST C DFLIST: DISTANCE LIST C KF : POINTER LIST FOR FLIST AND DFLIST C N : NUMBER OF NODES C MJ : ARRAY OF SHORTEST PATH LENGTHS C JO : INITIAL NODE, FIRST NODE OF SHORTEST PATH C WJ : ARRAY OF PREDECESSORS FOR SHORTEST PATH CONSTRUCTION C NJ : DOUBLE ENDED QUEUE FOR NODE DISCUSSION C INF : A LARGE NUMBER C C INITIAL VALUES OF C FLIST,DFLIST,KF: NETWORK FROM INPUT AND MAIN PROGRAM C N : NUMBER OF NODES FROM INPUT AND MAIN PROGRAM C J0 : START NODE FROM INPUT AND MAIN PROGRAM C DO 1 I=1,N MJ(I)=INF 1 NJ(I)=0 MJ(J0)=0 C C I : INDEX FOR NODE DISCUSSION, NODE UNDER DISCUSSION C NT : POINTER TO THE END OF DEQUE NJ C MJI : LOCAL VARIABLE OF MJ(I) C KFI : LOCAL VARIABLE OF KF(I) C KFI1 : LOCAL VARIABLE OF KF(I)+1 C IR : INDEX FOR ARRAY DISCUSSION C K : SUCCESSOR OF NODE I C MJK : LOCAL VARIABLE OF MJ(K) C NJI : LOCAL VARIABLE OF NJ(I), THE NEXT NODE OF NJ TO BE TAKEN C UNDER DISCUSSION C NJ(J0)=INF I=J0 NT=J0 C C OUTER LOOP C DISCUSSION OF NODES I C 2 KFI=KF(I+1) MJI=MJ(I) KFI1=KF(I)+1 C C INNER LOOP C DISCUSSION OF SUCCESSORS K C IF (KFI1.GT.KFI) GO TO 6 DO 5 IR=KFI1,KFI K=FLIST(IR) MJK=MJI+DFLIST(IR) C NO DECREASE OF SHORTEST DISTANCES IF (MJK.GE.MJ(K)) GO TO 5 C DECREASE OF SHORTEST DISTANCES MJ(K)=MJK C PREDECESSOR I OF NODE K WJ(K)=I C NODE K ALREADY IN THE DEQUE NJ ? IF (NJ(K)) 4,3,5 C NODE K ADDED AT THE END OF THE DEQUE NJ 3 NJ(NT)=K NT=K NJ(K)=INF GO TO 5 C NODE K ADDED AT THE BEGINNING OF THE DEQUE NJ 4 NJ(K)=NJ(I) NJ(I)=K IF (NT.EQ.I) NT = K 5 CONTINUE C NODE I TAKEN FROM THE BEGINNING OF THE DEQUE NJ 6 NJI=NJ(I) NJ(I)=-NJI I=NJI IF (I.LT.INF) GOTO 2 RETURN END SUBROUTINE SHPATH(J0,KE,WJ,H,NI,W) PAT00001 INTEGER WJ(50),H(50),W(50) C C SHPATH CALCULATES THE SHORTEST PATH BETWEEN THE TWO NODES J0 AND C KE. SHPATH USES THE INFORMATION IN WJ, THE LIST OF PREDECESSOR C NODES. THE NODES OF THE SHORTEST PATH ARE STORED IN W. C C J0 : FIRST NODE OF THE SHORTEST PATH C KE : LAST NODE OF THE SHORTEST PATH C WJ : ARRAY OF PREDECESSORS FOR SHORTEST PATH CONSTRUCTION C H : AUXILIARY ARRAY FOR THE SHORTEST PATH C NI : NUMBER OF NODES OF THE SHORTEST PATH C W : THE SHORTEST PATH C C I,J : LOCAL VARIABLE FOR NODE DISCUSSION C C INITIAL VALUES OF C J0 : FIRST NODE FROM INPUT OR MAIN PROGRAM C KE : LAST NODE FROM INPUT OR MAIN PROGRAM C WJ : FROM SUBROUTINE SHPTHL C H(1)=KE I=1 J=KE IF (J0.EQ.KE) GO TO 2 C 1 I=I+1 J=WJ(J) H(I)=J IF (J.NE.J0) GO TO 1 C 2 NI=I C DO 3 I=1,NI 3 W(I)=H(NI+1-I) C RETURN END