ベルマンフォード法 (Bellman-Ford Algorithm)

概要

重み付きグラフ\(G = (V, E)\)の始点\(v_s\)から終点\(v_t\)への最短経路を求める。

辺のコストに負が含まれていても正しく動き、負閉路も検出することができる。

計算量

\(O(|V||E|)\)

実装

# V: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
dist = [INF] * V
dist[r] = 0
update = 1
for _ in range(V):
    update = 0
    for v, e in enumerate(G):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break
else:
    # 負閉路検出処理
    ...

Verified

  • AOJ: "GRL_1_B: Shortest Path - Single Source Shortest Path (Negative Edges)": source (Python2, 0.52sec)