Dijkstraで重み付き最短路

非負の重みでは、最小の暫定距離の頂点を確定できます。小さい値を取り出すヒープを使います。

言語：Python / 計算量：O((V+E) log V)（単純グラフ）

前提：BFSで重みなし最短路 / ヒープで今の最小値を取る

考え方

1. 距離配列を無限大、始点を0。
2. ヒープから最小の距離を取り出します。
3. 距離が改善した隣接頂点だけ再び入れます。

具体例

0→1が5、0→2が1、2→1が1なら、1への最短は直行の5ではなく2です。

実装

import heapq
g = [[(1,5),(2,1)],[],[(1,1)]]
d = [float("inf")]*3;d[0]=0
h = [(0,0)]
while h:
    cost,v=heapq.heappop(h)
    if cost != d[v]:continue
    for u,w in g[v]:
        nd=cost+w
        if nd<d[u]:
            d[u]=nd;heapq.heappush(h,(nd,u))
print(d[1])

注意する条件

負の辺がある場合はこの確定の論理が壊れます。古いヒープ要素をスキップしないと遅くなります。

確認問題

例の頂点0から1への最短距離は？

実装課題

N M と有向辺 u v w（0始まり、非負）。0からN-1の最短距離、到達不能なら-1。N,M ≤ 200000、w ≤ 10^9。

入力:
3 3
0 2 5
0 1 1
1 2 1
出力:
2

import heapq
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v,w=map(int,input().split());g[u].append((v,w))
d=[float("inf")]*n;d[0]=0;h=[(0,0)]
while h:
    cost,v=heapq.heappop(h)
    if cost!=d[v]:continue
    for u,w in g[v]:
        if cost+w<d[u]:
            d[u]=cost+w;heapq.heappush(h,(d[u],u))
print(-1 if d[-1]==float("inf") else d[-1])

読了の記録・下書き・メモへ