AOJ pythonでダイクストラ法の勉強
・ダイクストラ法の詳しい解説:グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube
・やること:ダイクストラ法のプログラムの勉強のため上のAOJの問題を解く。
・プログラムの説明:はじめに辺がないときの処理をする。またG[s]にsからいける点tとその重さdを入れる。rから始めるのでdequeにrを入れてdist[r]=0(重さが0からスタート)で重さの最小値を更新していく。
・実装例:
from collections import deque v,e,r=map(int,input().split()) #頂点数と辺、始点 #辺がないとき、始点の番号以外はINF。 if e==0: for i in range(v): if i==r: print(0) else: print("INF") exit() G=[[] for _ in range(v)] for i in range(e): s,t,d=map(int,input().split()) G[s].append((t,d)) #sからいけるのがt。dはその重さ。 #print(G) #入力は一個目のテストケースで[[(1, 1), (2, 4)], [(2, 2), (3, 5)], [(3, 1)], [], []] #for i in range(e): # for j,k in G[i]: # print(j,k) #1 1,2 4,2 2,3 5,3 1 dist=[10**18 for _ in range(v)] #distは辺の重さの最小の合計 dist[r]=0 que=deque() que.append(r) while len(que)!=0: pl=que.popleft() #plから行ける点がp、その重さがl for p,l in G[pl]: #上のコメントアウト参照 d=dist[pl]+l #distが更新できるなら if d<dist[p]: dist[p]=d que.append(p) #出力 for i in range(v): if dist[i]==10**18: print("INF") else: print(dist[i])