Day 140-Q2 | Johnson's Algorithm

問題

$N$ 頂点 $M$ 辺の有向重み付きグラフが与えられる。辺の重みは負の場合があるが、負閉路は存在しないことが保証されている。

全点対 $(s,t)$ について、$s$ から $t$ への最短距離を求めよ。$t$ に到達できない場合は INF と出力せよ。

素朴に全頂点から Bellman-Ford 法（$O(NM)$）を行うと全体で $O(N^2 M)$ かかるが、これをより高速化する Johnson のアルゴリズムを実装して解け。

手順:

全頂点へ重み0の辺を張る仮想頂点でBellman-Fordを実行しポテンシャル $h(v)$ を求める
各辺を $w'(u,v)=w(u,v)+h(u)-h(v)$ で重み付け替え（負閉路が無ければ必ず非負になる）
重み付け替え後のグラフに対し、全頂点を始点としてDijkstra法を実行
真の距離は $d(s,t)=d'(s,t)-h(s)+h(t)$ で復元

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M

制約

$1 \le N \le 300$

$0 \le M \le 2000$

$-10^4 \le w_i \le 10^4$

負閉路なし

入出力例

入力例1

出力例1

0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

入力例2

3 2
0 1 2
1 2 -1

出力例2

0 2 1
INF 0 -1
INF INF 0

概念図

ヒント（段階的開示）

ヒント1（方向性）

負辺があると Dijkstra 法は正しく動かない。かといって全頂点から Bellman-Ford を回すのは $N$ が大きいと遅すぎる。「グラフ全体の辺重みを、最短路の大小関係を変えずにすべて非負にできれば、あとは Dijkstra を $N$ 回回すだけで済む」という発想がこのアルゴリズムの出発点である。

ヒント2（アプローチ）

各頂点にポテンシャル $h(v)$ を割り当て、辺 $(u,v,w)$ の重みを $w'=w+h(u)-h(v)$ に置き換えると、任意の経路の重み付け替え後の総和は元の総和から $h(s)-h(t)$ を引いた値に必ず一致する（途中の$h$がすべて打ち消し合う）。$h(v)$ = 「全頂点に0コストで行ける仮想始点からの最短距離」に取ると、三角不等式 $h(v)\le h(u)+w(u,v)$ が保証され、これはちょうど $w'\ge 0$ を意味する。

ヒント3（誘導）

# Step1: 仮想頂点nからBellman-Ford（hを全頂点0で初期化するだけでよい）
h = [0]*(n+1)
for _ in range(n):
    for u, v, w in edges:
        if h[u] + w < h[v]:
            h[v] = h[u] + w

# Step2: 重み付け替え
adj = [[] for _ in range(n)]
for u, v, w in edges:
    adj[u].append((v, w + h[u] - h[v]))

# Step3+4: 全頂点からDijkstra、距離を復元
for s in range(n):
    d = dijkstra(adj, s)
    for t in range(n):
        真の距離[s][t] = d[t] - h[s] + h[t]

模範解答 (Python)

import sys
import heapq

def main():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    edges = []
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))

    INF = float('inf')

    h = [0] * (n + 1)
    for _ in range(n):
        updated = False
        for u, v, w in edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w
                updated = True
        if not updated:
            break

    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        nw = w + h[u] - h[v]
        adj[u].append((v, nw))

    result = []
    for s in range(n):
        dist = [INF] * n
        dist[s] = 0
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        row = []
        for v in range(n):
            if dist[v] == INF:
                row.append('INF')
            else:
                row.append(str(dist[v] - h[s] + h[v]))
        result.append(' '.join(row))

    print('\n'.join(result))

main()

Step-by-Step 解説

1なぜ仮想頂点からのBellman-Fordで十分か
仮想頂点$N$から全頂点へ重み0の辺を張ると、$h(v)=d(N,v)$ は「$v$に到達するための最小コスト」であり、任意の辺$(u,v,w)$について三角不等式 $h(v)\le h(u)+w$ が必ず成り立つ。実装上は仮想頂点を作らず$h$を全頂点0で初期化するだけで同じ結果が得られる。

2重み付け替えで負辺が消える理由
$w'(u,v)=w(u,v)+h(u)-h(v)$ とすると、三角不等式より $w'(u,v)=w(u,v)-(h(v)-h(u))\ge 0$ が常に成り立つ。

3経路の総重みが保たれる理由（テレスコーピング）
経路の$w'$上での総和は $\left(\sum w(v_{i-1},v_i)\right)+h(v_0)-h(v_k)$ の形になり、中間の$h$がすべて打ち消し合う。したがって $d(s,t)=d'(s,t)-h(s)+h(t)$ で真の距離を復元できる。

4Dijkstraを$N$回回す
$w'$が非負になったのでDijkstra法（$O(M\log N)$）が使える。全始点分で $O(NM\log N)$ となり、単純な全点対Bellman-Fordの$O(N^2M)$より大幅に高速。

5到達不能の扱い
DijkstraでINFのまま残った頂点は真の距離でも到達不能である（$h$による補正は有限値同士の演算なので到達可否に影響しない）。

よくあるミス

ミス	原因	正しい書き方
仮想頂点を作らずhの初期値をINFにしてしまう	通常のBellman-Fordの感覚を持ち込む	hの初期値は全頂点0が正しい
重み付け替えを符号逆に書いてしまう	加減の向きを覚え間違える	正しくは`w + h[u] - h[v]`。三角不等式から導出して確認する
復元時に符号を逆にする	付け替え式の逆算を誤る	$d(s,t)=d'(s,t)-h(s)+h(t)$ が正しい。$s=t$で検算できる
到達不能な頂点にも補正をかけて謎の数値を出力	INF判定を距離補正前に行わない	補正前に必ずINF判定を行う
負閉路があるケースで無限ループする	制約を信じ収束チェックを省略	本問では保証されているが、実務ではN回目の反復で更新があるか確認する習慣をつける

次のステップ

発展: 負閉路が存在する可能性がある入力に対して、Bellman-Fordの収束チェックを追加し、負閉路を検出したら-1を出力するよう拡張せよ。
発展2: Mが非常に大きい密グラフの場合、Johnson法よりワーシャルフロイド法（$O(N^3)$）の方が定数倍で有利になる境界を実測で確認せよ。

自己評価

完全理解おおむね理解要復習

Day 140-Q2 — Johnson's Algorithm（負辺を含む全点対最短路）

問題