Pythonでダイクストラ法を書いて半日を無駄にした話
FEの教科書を読んでいて、ダイクストラとかいうやつがわけわかんなかったから自分で書いてみるしかなかった。ダイクストラってなんだよ。ローマの思想家?あとPython、インデックス0からなのほんとにやめてねー。とりあえず教科書の図通りで書いてはみたものの、無駄が多すぎる気しかしない。あと、教科書で距離を無限大に定義してたから、sys.maxsizeとか書いたけど、こんなん書いても大丈夫なんか???
import sys
def disktra(N: int, C: list):
# Nはポイントの個数、Cは各ポイント間の距離を定義した二次元配列。1からNへの最短経路を求める。
D = [0]*(N)
P = [0]*(N)
S = [0]*(N)
W = [0]*(N)
# 初期設定
for i in range(N):
D[i] = C[0][i]
P[i] = 0
S[i] = 0
# 最短経路を求める
for l in range(N):
P[0] = 1
p = 0
dmin = sys.maxsize
# Dの最小を選ぶ
for i in range (N):
if P[i] == 0 and D[i] < dmin:
p = i
dmin = D[i]
P[p] = 1
# 次のやつを選ぶ
for m in range (N):
if P[m] == 0 and dmin + C[p][m] < D[m]:
D[m] = dmin + C[p][m]
S[m] = p
print (D, P, S)
# 出力
X = 0
Y = N-1
while Y != 0:
W[X] = Y
Y = S[Y]
X = X + 1
W[X] = Y
while X > -1:
print(W[X])
X = X - 1
G = [[sys.maxsize, 30, sys.maxsize, 20, 120],
[sys.maxsize, sys.maxsize, 70, sys.maxsize, sys.maxsize],
[sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 30],
[sys.maxsize, sys.maxsize, 50, sys.maxsize, 90],
[sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize]]
disktra(5, G)
この記事が気に入ったらサポートをしてみませんか?