ダイクストラ法：ソフトウェアデザイン 10月号のけんちょんさんの記事内容を元にPythonでAOJの問題を問いてみた - Qiita

解いた問題 ソース AOJの問題は始点の指定があることに注意 蟻本ではフラグを使って更新の有無を確認していたが、けんちょんさんのやり方は、更新されなければ確定（優先度付きキューに入れない）という手法。 優先度付きキューをpopして取得した頂点（スタートからの距離が最小の頂点）から探索をする。 import heapq INF = 10**10 class Edge: to = -1 w = -1 def __init__(self, to, w): self.to = to self.w = w def Dijkstra(Graph, s): dist = [INF] * len(Graph) dist[s] = 0 prev = [-1] * len(Graph) #スタート頂点をキューに入れる #[該当頂点までの最短距離（現時点）,該当頂点のインデックス] que = [[0,s]]