Coding Interview Prep · レッスン

Bellman-Fordと負閉路

Q: 「Bellman-Fordと負閉路」レッスンは無料ですか？

はい。「Bellman-Fordと負閉路」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

Q: 「Bellman-Fordと負閉路」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

すべての辺に対してn-1回の緩和を行い、最後の1回で負閉路を検出し、負の重みを持つ辺でDijkstraが失敗する理由を説明します。

「Bellman-Fordと負閉路」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Bellman-Ford が存在する理由

Bellman-Ford は Dijkstra と同じく単一始点最短経路問題を解きますが、負の辺の重みを扱えます。また、負の閉路も検出できます。負の閉路とは、合計の重みが負になる閉路であり、その中を通る有限な最短経路を定義できなくなります。Dijkstra より低速ですが、グラフに負の重みを持つ辺が含まれる可能性がある場合は、Bellman-Ford が正しい選択です。

緩和：中心となる操作

Bellman-Ford は、1つの操作を中心に構成されています。それが緩和です。辺 (u, v, w) の緩和とは、dist[u] + w < dist[v] なら dist[v] = dist[u] + w に更新することです。これをすべての辺に対して繰り返し行います。重要な点は、負の閉路がないグラフでは、どの最短経路も高々 V-1 本の辺で構成されることです。したがって、すべての辺に対して V-1 回の緩和を行えば、すべての最短経路を求められます。

Bellman-Ford の実装

グラフは辺のリスト [(u, v, weight)] として表現します。dist[source] = 0 と初期化し、それ以外はすべて inf にします。V-1 回のラウンドを実行し、各ラウンドですべての辺を緩和します。V 回目のラウンドでも更新が発生する場合は、負の閉路が存在することを示します。

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

V-1 回のパスで十分な理由

負の閉路がないグラフの最短経路では、各ノードを高々1回しか訪れないため、辺の数は高々 V-1 本です。1ラウンド後には、1ホップの最短経路が最適になります。2ラウンド後には、2ホップの最短経路が最適になります。V-1 回のラウンド後には、高々 V-1 ホップで構成されるすべての最短経路が求まります。V 回目のラウンドでも距離が更新される場合、グラフには始点から到達可能な負の閉路があります。

負の閉路の検出

V-1 回のパスの後、すべての辺に対して追加で1回パスを実行します。辺 (u, v, w) のいずれかで dist[u] + w < dist[v] が成り立つ場合、負の閉路が存在し、一部のノードへの最短経路は -∞ になります。現実世界での応用例には、通貨交換における裁定取引の機会の検出（対数重みグラフにおける負の閉路）や、制約システムの矛盾の検出があります。

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

Dijkstra と Bellman-Ford の比較

Dijkstra：O((V+E) log V)、非負の重みが必要、貪欲法。Bellman-Ford：O(V × E)、負の重みを扱え、負の閉路を検出できます。非負の重みを扱う面接問題の多くでは、Dijkstra が適しています。負の重みが現れる場合（例：「負のコストの辺を含む最短経路を求める」や「裁定取引を検出する」）は、Bellman-Ford が答えです。密グラフでは、Bellman-Ford の最悪計算量 O(V³) は Floyd-Warshall と同程度です。

応用：Bellman-Ford による最安フライトの計算

「K回以内の乗り継ぎで最安のフライト」（LeetCode 787）は、Bellman-Ford を変更して解けます。k+1 回の緩和パスを正確に実行します（k 回の乗り継ぎは k+1 本の辺を意味するためです）。1回のパスで許可されたホップ数を超えないように、前のパスの距離のコピーを使います。そうしないと、1回のパスで複数のホップを連鎖させてしまう可能性があります。

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA：キューを使った最適化

Shortest Path Faster Algorithm（SPFA）は、距離が直前に更新されたノードから出る辺だけをキューを使って再度緩和する、最適化された Bellman-Ford です。平均計算量は O(E) ですが、最悪計算量は O(V × E) のままです。SPFA が面接で必要になることはほとんどありませんが、疎グラフで Bellman-Ford が遅すぎる場合の最適化として言及できるでしょう。Python には組み込みの SPFA はありませんが、collections.deque を使えば簡単に実装できます。

通貨裁定取引の検出

Bellman-Ford の典型的な応用例です。通貨の交換レートが与えられたとき、裁定取引が可能かどうかを検出します。これは、通貨を交換すると開始時より多くの金額が戻ってくる閉路です。交換レートの負の対数を取って変換します。裁定取引は、対数重みの合計が負の閉路、つまり Bellman-Ford で検出できる負の閉路に相当します。これにより、現実の金融問題を標準的なアルゴリズムに対応付けられます。

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

早期終了の最適化

すべての辺に対する1回のパスで距離が1つも更新されなければ、その後のパスでも何も更新されないため、そこで早期終了できます。この最適化により、グラフが数回のパスですでに最適な状態になる場合、最良計算量を O(E) まで削減できます。各パスの開始時に updated = False というフラグを追加し、パスの後も False のままなら、直ちにループを抜けます。

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

隣接リストを使ったグラフでの Bellman-Ford

グラフが辺のリストではなく隣接リストで与えられる場合は、最初に辺のリストへ変換するか、隣接リストのすべての要素を辺として走査します。V=1000、E=5000 の場合、V-1=999 回のパスで毎回 5000 本の辺を走査するため、操作数は 4,995,000 になります。これは制限時間内に十分収まる範囲です。非常に密なグラフ（E ≈ V²）では、最悪計算量 O(V³) が Floyd-Warshall と一致するため、どちらを選ぶかは状況によって決まります。

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、Bellman-Ford はすべての辺を V-1 回緩和して負の重みを持つ辺を扱うこと、V 回目の緩和パスでも改善が見つかる場合は負の閉路を示すこと、そしてアルゴリズムの計算量は O(V × E) で、Dijkstra の O((V+E) log V) と比較されることを学びました。次は、1回の O(V³) の計算で全点対最短経路を求める Floyd-Warshall を取り上げます。

よくある質問