heapを使ったダイクストラ法の計算量について考える - Qiita

# 既にその頂点までの最低コストが確定している場合、頂点番号のindex要素をTrueとします。 seen = [False for _ in range(V)] # その頂点までのコストを管理します。 C = float("Inf") cost = [C for _ in range(V)] cost[0] = 0 # (コスト, 頂点番号) heap = [(0, 0)] # Gは辞書型で、頂点0→頂点1のコストが10の場合、G[0][1] = 10としています。 while heap: s = heappop(heap)[1] seen[s] = True for i in G[s].keys(): if cost[i] > cost[s] + G[s][i] and not seen[i]: cost[i] = cost[s] + G[s][i] heappush(heap, (c