グラフに対するアルゴリズム。非負の重みを持つグラフにおいて、単一始点から各頂点への最短経路を求めることができる。例えば、都市間の最短ルートを計算する場合などである。手順は以下の通りである。

1. 未確定頂点の中でその頂点へ行くための距離が最も小さい頂点を求める
2. 1で求めた頂点に隣接する頂点について、その頂点へ行くための最小距離を求める。

「未確定頂点の中で距離が最も小さい頂点を求める」という性質上、優先度付きキューを組み合わせて使うことがしばしば。優先度付きキューは別Wikiを参照。

例題: ABC214 C

C - Distribution

解説の画像を拝借する。

今回は単一方向にのみつながっている円構造だ。いきなり話の腰を折るが、この場合は単純な配るDPで解くことができ、しかもその方が計算量も少ない。計算量はO(N)だ。2周するのは、1番目の頂点がt時にもらうより、N番目の頂点から1番目の頂点へ渡す方が早い場合があるからだ。

n = int(input())

s = list(map(int, input().split()))
t = list(map(int, input().split()))

for i in range(2*n):
    t[(i+1) % n] = min(t[(i+1) % n], t[i % n] + s[i % n])

for i in range(n):
    print(t[i])

今回ダイクストラ法を使うとheappopにO(logN)かかり、各頂点を1回は訪れることになるため計算量はO(N log N)となる。そのため上記よりも計算が遅い。実際の回答結果を見ても1行目のダイクストラ法の結果の方が時間がかかっている。

が、単方向なぶんダイクストラ法の感覚を掴むにはやりやすい。ので、実装してイメージを掴んでみる。

import heapq

n = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

# ダイクストラ法のための優先度付きキュー
pq = []
for i in range(n):
    heapq.heappush(pq, (T[i], i))  # (現在の最短時間, 頂点)

# ダイクストラ法の実行
while pq:
    time, u = heapq.heappop(pq)  # 現在の最小時間の頂点を取り出す
    
    # 次の頂点 (環状なので (u+1) % n)
    v = (u + 1) % n
    new_time = time + S[u]  # u から v へ行くコストを加算
    
    # より短い時間で v に行ける場合、更新する
    if new_time < T[v]:
        T[v] = new_time
        heapq.heappush(pq, (T[v], v))  # 更新後の情報をキューに追加

# 結果の出力
for t in T:
    print(t)

今回の場合と違いダイクストラ法が威力を発揮してくれるのは複数方向に移動する場合だ。その時は1頂点に対する辺の数がM(0以上)となる。が、そうなってもheappushがM増えるだけなので、計算量はO(N+M log N)