|
|
https://ja.wikipedia.org/wiki/ダイクストラ法
ダイクストラ法によるグラフ探索です。
このプログラムは移植版です。
DIM NODE$(26)
MAT READ NODE$
DATA A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z
RESTORE 10
READ SIZE
DIM VISITED(SIZE),DISTANCE(SIZE),INDEX(SIZE),A(SIZE,SIZE)
LET TRUE=1
LET FALSE=0
LET INF=100000000
MAT DISTANCE=(INF)*CON
FOR I=1 TO SIZE
FOR J=1 TO SIZE
READ S$
IF S$<>"INF" THEN LET A(I,J)=VAL(S$) ELSE LET A(I,J)=INF
NEXT J
NEXT I
LET START=3
LET DISTANCE(START)=0
LET NEXTINDEX=START
DO
LET I=NEXTINDEX
LET VISITED(I)=TRUE
LET LMIN=INF
FOR J=1 TO SIZE
IF VISITED(J)=FALSE THEN
IF A(I,J)<>INF AND DISTANCE(J)>DISTANCE(I)+A(I,J) THEN
LET DISTANCE(J)=DISTANCE(I)+A(I,J)
LET INDEX(J)=I
END IF
IF DISTANCE(J)<LMIN THEN
LET LMIN=DISTANCE(J)
LET NEXTINDEX=J
END IF
END IF
NEXT J
LOOP WHILE LMIN<INF
FOR I=1 TO SIZE
IF I<>START AND VISITED(I)=TRUE THEN
LET K=I
PRINT NODE$(K);
DO
LET K=INDEX(K)
PRINT " ← ";NODE$(K);
LOOP UNTIL K=START
PRINT " DISTANCE";DISTANCE(I)
END IF
NEXT I
10 DATA 10 ! 有向グラフ
DATA INF, 1, 4,INF, 5,INF, 2,INF, 2,INF
DATA INF,INF, 3,INF,INF, 4,INF,INF,INF,INF
DATA 3,INF,INF, 2,INF,INF, 1,INF,INF, 1
DATA INF,INF, 2,INF,INF,INF,INF, 3,INF,INF
DATA INF, 2,INF,INF,INF, 2,INF,INF,INF, 1
DATA 1,INF, 4,INF, 1,INF, 5,INF,INF,INF
DATA INF, 3,INF,INF,INF, 6,INF, 5,INF,INF
DATA 1,INF,INF, 3,INF,INF,INF,INF, 5,INF
DATA INF, 2,INF, 5,INF, 2,INF, 3,INF, 2
DATA 1,INF, 4, 3,INF,INF, 5,INF,INF,INF
20 DATA 8 ! 無向グラフ(対角成分に対して対称。A(I,J)とA(J,I)が同値)
DATA INF, 1, 1,INF,INF,INF, 1, 1
DATA 1,INF, 1,INF, 1,INF,INF,INF
DATA 1, 1,INF, 1,INF, 1, 1,INF
DATA INF,INF, 1,INF, 1,INF, 1, 1
DATA INF, 1,INF, 1,INF, 1,INF,INF
DATA INF,INF, 1,INF, 1,INF, 1,INF
DATA 1,INF, 1, 1,INF, 1,INF, 1
DATA 1,INF,INF, 1,INF,INF, 1,INF
30 DATA 10 ! 有向グラフ
DATA INF, 2,INF, 1,INF, 4, 6,INF, 7,INF
DATA INF,INF,INF, -2, 1,INF,INF, 2,INF, 1
DATA -3,INF,INF,INF, 1,INF, -1,INF, 2,INF
DATA INF, 2,INF,INF,INF,INF, 1,INF,INF, 3
DATA INF,INF, -1,INF,INF, 2,INF, 3, 4,INF
DATA 4,INF,INF,INF, 2,INF,INF, 1,INF, 5
DATA INF, 1,INF, 2,INF, 1,INF, 5,INF,INF
DATA 2,INF,INF, 4,INF, 3,INF,INF, 2, 4
DATA INF,INF, 4,INF, 4,INF, -2,INF,INF,INF
DATA 1,INF, 3,INF, 6,INF, 1,INF,INF,INF
40 DATA 7
DATA INF, 1,INF, 3,INF, 5,INF
DATA 2,INF, 3,INF,INF,INF, 2
DATA INF, 2,INF, 2, 4,INF,INF
DATA INF,INF, 4,INF,INF,INF, 5
DATA 3,INF, 3, 3,INF, 2,INF
DATA INF, 1,INF, 4, 2,INF,INF
DATA 5,INF, 2,INF, 3, 6,INF
END
|
|