dijkstra法備忘録

はじめに

atcoderでよく登場するので，備忘録としてまとめました．

ダイクストラ法(dijkstra's algorithm)の問題と戦略

＜問題＞

出発点を一つ固定して，この頂点から他のすべての頂点への最短経路を求める問題を考える．

＜戦略＞

各頂点への最短路を出発点に近い(短い)ところから一つずつ確定していく

\def\set#1{\left\{{#1}\right\}}

例

頂点集合$V=\set{A,B,C,D,E,F}$と辺の集合が$E = \set{(A,B),(A,C),(B,D),(C,E),(C,F),(E,B),(E,D)}$となる重み付きの有向グラフを考える．

例えば，点Aから点Bへ行くには6km歩かなければならないようなグラフになっている．
この例での移動は一方通行(有向グラフ)であるが，ダイクストラ法は対面通行(無向グラフ)でも使用できる．

確定させる点の順番

最短経路が確定した順に赤く塗りつぶしている．

ダイクストラ法を使う問題例(ABC-252-E)

＜問題概要＞

N個の都市とその都市を結ぶM本の道路を考える．都市1からそれ以外の各都市へ移動するまでの最短経路のみを残すとき，残した道路を出力してください．

＜戦略＞

dijkstra法を回している途中で，使われた道路を記録していく．

Python3を使った実装

実行時間 - メモリ：1357ms - 196832KB

from heapq import heappop, heappush, heapify

N,M = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(1,M+1):
    s,t,d = map(int,input().split())
    G[s-1].append((d,t-1,i))
    G[t-1].append((d,s-1,i))

l = [0]*N
def dijkstra(s):
    hq = [(0,s,0)] #(道路の長さ,出発点,道路番号)
    heapify(hq)
    cost = [10**20] * N
    cost[s] = 0
    while hq:
        c,v,e = heappop(hq)
        if c > cost[v]:
            continue
        l[v] = e
        for d, u, r in G[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heappush(hq,(tmp,u,r))
    return cost

dist = dijkstra(0)

ans = []
for i in l:
    if i>=1:
        ans.append(i)
print(*ans)