あくまで備忘録なんで雑に記録しますダイクストラ法
・全ての地点マップcost_map（初期値inf）：s(スタート)からのcostリスト
・hq=heapq：いったん入れていくキュー、現在地からの(tmp,目的地)を全部push
・インデックスを始点として、[cost,終点]を双方向にリストinリスト
以上の３つを用意
①地点マップの始点に０を書き込む
hqにスタート(0, s)を入れる
<while hq:>
②未確定の地点の中から最も小さい値を持つ地点を選び、その時点でその値を確定させる
ここで確定させられる理由は、０から辿れるpoint_cost(拠点コスト)の最小値から順にpopするので、他ルートからそれ以下で辿れる事はないから
また閉路で既に訪問済みの場合、小さければcontinue（スキップ）
③②で確定した地点から直接接続に対して”時間（距離）”を計算し、小さければ更新
以下②を繰り返す
④全ての地点が確定（キューがなくなる）していれば終了
ここで気になるのが、最初のwhileで０(N)
拠点の数がN個だとすると、０(N^2)
heapqを使えば、最小値を取り出すのに０(１)
n,m = map(int,input().split())#拠点数ｎ、経路数ｍとして
vector_list = [[] for _ in range(n)]
#入力するa, b, t = (出発地, 目的地, cost)となる
for _ in range(m):
a,b,t = map(int,input().split())
#インデックスを始点として、[cost,終点]を双方向リストinリスト
vector_list[a].append([t, b])
vector_list[b].append([t, a])
import heapq
def dijkstra(s): #O(N^2)
hq = [(0, s)] #(point_cost, 出発地の初期値としてのスタート地点)を投入
heapq.heapify(hq) #リストを優先度付きキューに変換
cost_map = [float('inf')] * n #行ったことのないところは'inf'
cost_map[s] = 0 #開始地点は0
while hq:
point_cost, start = heapq.heappop(hq) #重み付きヒープ内(point_cost, 出発地)最小値を現在地（確定）としてpop
if point_cost > cost_map[start]: #順番が来ても既に更新されていたら次のhqへ
continue
for travel_cost, end in vector_list[start]: #現在地から、たどれるリスト内リストを全部まわす
tmp = travel_cost + cost_map[start] #リスト内リストのcost＋現在地のコストを一時tmp
if tmp < cost_map[end]: #コストマップがtmpで更新されるなら置き換え
cost_map[end] = tmp
heapq.heappush(hq, (tmp, end)) #(その更新されたtmp, 目的地：次回の出発値)達を追加
#この後、その最小tmpの目的地がpopされる（つまり確定）
#いずれ全infはtmpに置き換わり、heapqから小さい順にpopされる（確定）
#同じ目的地の(tmp, 目的地)が複数heapqにある事もあるが、最初のifでcontinueされる
return cost_map
インプット・アウトプット例
'''インプットを下記(a0 ~ am)
(n, m) = (0~7のノード, 0~10のエッジ)
(a, b, c) = (start, vector, cost)
8 11
0 1 5
0 2 4
0 3 1
1 4 2
2 3 2
2 4 5
2 5 6
4 6 1
4 7 3
5 7 2
6 7 4
'''
print(dijkstra(0))
#[0, 5, 3, 1, 7, 9, 8, 10]
for i in range(n):
print(i,'が出発地での(cost,目的地)', vector_list[i])
# 0 が出発地での(cost,目的地) [[5, 1], [4, 2], [1, 3]]
# 1 が出発地での(cost,目的地) [[5, 0], [2, 4]]
# 2 が出発地での(cost,目的地) [[4, 0], [2, 3], [5, 4], [6, 5]]
# 3 が出発地での(cost,目的地) [[1, 0], [2, 2]]
# 4 が出発地での(cost,目的地) [[2, 1], [5, 2], [1, 6], [3, 7]]
# 5 が出発地での(cost,目的地) [[6, 2], [2, 7]]
# 6 が出発地での(cost,目的地) [[1, 4], [4, 7]]
# 7 が出発地での(cost,目的地) [[3, 4], [2, 5], [4, 6]]
コメント