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

概要

単一始点最短経路問題(SSSP)を解くアルゴリズム。

重み付きグラフ \(G = (V, E)\) の始点 \(v_s\) から各頂点 \(v_t\) への最短距離を求める。
辺のコストに負が含まれていても正しく動き、負閉路も検出することができる。

計算量

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

実装

# N: グラフの頂点数
# r: 始点
# G[v] = [(w, cost), ...]: 頂点vからコストcostで到達できる頂点w
INF = 10**18
def bellman_ford(N, G, r):
    dist = [INF] * N
    dist[r] = 0
    update = 1
    for _ in range(N):
        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)

戻る