Bellman–Ford

すべての辺での緩和を $N - 1$ 回繰り返して最短距離を求めたあと、さらに $N$ 回繰り返して、まだ小さくできる頂点（負閉路を通っていくらでも小さくできる頂点）を $-\infty$ にします。途中で更新がなくなったら、その時点で打ち切ります。

• bellman_ford(n, edges, s): 頂点数 $n$、有向辺のリスト edges = [(u, v, w), ...]、始点 $s$ から、各頂点への最短距離のリストを返す。到達できない頂点は INF（ $= 2^{60}$）、負閉路の影響でいくらでも小さくできる頂点は -INF
• 計算量: $O(NM)$

$s$ から到達できる負閉路があるかは、-INF in dist で判定できます。

コード

INF = 1 << 60


def bellman_ford(n, edges, s):
    # edges = [(u, v, w), ...]（有向）
    # 到達できない頂点は INF、負閉路を通っていくらでも小さくできる頂点は -INF
    dist = [INF] * n
    dist[s] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            return dist
    for _ in range(n):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = -INF
    return dist