グラフ系アルゴリズム:ベルマン・フォード法

今回は競技プログラミングの記事です。

グラフのある1点から、他のすべての点への最短距離を求められるアルゴリズム、ベルマン・フォード法(Bellman–Ford algorithm)のご紹介です。

ダイクストラ法では、グラフのすべての辺のコストが非負である必要がありましたが、ベルマン・フォード法の場合はコストが負の辺が含まれていても機能します。その代償に、計算量が  O(VE) となります。なお、 V はノードの個数、 E は辺の個数です。

それでは早速スクリプトをどうぞ。

import math

class BellmanFord:
    def __init__(self, graph):
        self.n = len(graph)
        self.graph = graph

    def solve(self, start):
        dp = [math.inf] for _ in range(self.n)]
        dp[start][0] = 0
        has_negative_loop = True
        for _ in range(self.n):
            updated = False
            for i, edges in enumerate(self.graph):
                for j, cost_i2j in edges:
                    cost_s2j = dp[i] + cost_i2j
                    if cost_s2j < dp[j]:
                        dp[j] = cost_s2j
                        updated = True
            if not updated:
                has_negative_loop = False
                break
        return has_negative_loop, dp

使い方は以下のようになります。

# graph は隣接リストでご用意ください。
graph = [[[...]]]

b = BellmanFord(graph)
# 距離を測りたい始点のインデックスを渡してください。
x = 0
b.solve(x)
# => True, [d0, d1, ... dn-1]
# 負閉路が含まれているか否かのフラグと、x から各点への最短距離がリストで手に入ります。
# フラグが False の場合、各点への最短距離リストはでたらめになっているのでご注意ください。

さて、スクリプトを見てみますと、結構力押しのアルゴリズムであることがわかります。「今わかっている始点  x から各点への最短距離をもとに、さらに短い距離で行ける点がないか全辺を探索する」という処理を  V 回繰り返します。

なぜこれで最短距離および負閉路の有無が求まるのかといいますと、

(1)
まず、閉路が存在しない場合、始点から任意の点への最短距離の経路上の辺の本数は、必ず  V-1 本以下となります。

そのため、閉路が存在しない場合は  V-1 回目のループ以内で、最短距離を通る経路を通ってすべての点にたどり着くことができます。

(2)
逆に閉路が存在する場合も、その閉路がすべて正閉路である場合、その閉路を通って同じ点にたどり着いたとしても、はじめにたどり着いたとき(=閉路を経由しないとき)よりも、2回目以降にたどりついたとき(=閉路を経由したとき)の方が、経路の距離が大きくなります。

閉路を経由しない場合、その経路上の辺の数は、閉路が存在しない場合と同じく  V-1 本以下となるので、  V-1 回目のループ以内で最短経路を通る経路でたどり着いているはずです。

(3)
最後に、負閉路が1つでも存在する場合、正閉路しか存在しない場合と異なり、今度ははじめにたどり着いたとき(=閉路を経由しないとき)よりも、2回目以降にたどりついたとき(=閉路を経由したとき)の方が、経路の距離が小さくなります。

特に、負閉路上のノードのことを考えると、負閉路上のノードのうちひとつでも2回目の更新が起きると、以降すべてのループで、負閉路上のいずれかのノードの最短距離が更新され続けます。

負閉路上のノードにおける2回目の更新は、最短  V 回目のループもしくはそれ以前のループで発生します。これは、負閉路を形成するノードが  k 個あるとして、始点から負閉路のいずれかのノードに初めてたどり着くような、閉路(正閉路含む)を経由しない経路上の辺の数が、高々  V - k 個にしかならないことから証明されます。

以上より、

  •  V 回目の更新が発生する  \Leftrightarrow グラフ内に負閉路が存在する。
  • グラフ内に負閉路が存在しない  \Leftrightarrow  V-1 回以内のループで、最短距離が求まる

ことが示されました。