Day 105-Q1 — Suurballe's Algorithm（辺素な最短路対）

2026-07-28 赤色 Master / Phase 8+ ★★★★★★★★★ 最小費用流によるSSP法・ポテンシャルダイクストラ

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺$i$は頂点$u_i$から$v_i$へ向かう重み$w_i$（$w_i\ge1$）の辺である。頂点$s$から$t$へ向かう2本の辺素な（同じ辺を2度使わない）有向パスを選び、その合計長を最小化せよ。辺素な2本のパスが作れない場合は$-1$を出力する。頂点の共有は許されるが、辺の共有は禁止される。

この問題は「容量1・コスト$w_i$の各辺を使い、$s$から$t$へ2単位の流量を最小コストで流す」問題と数学的に一致する。すべての重みが非負なので、successive shortest augmenting path 法をポテンシャル付きダイクストラで2回実行すればよい。1回目の最短路木の辺を残余グラフ上で逆向き・コスト0に張り替えてから2回目を探すという手続きは、歴史的に Suurballe's Algorithm（1974年）として知られる。

入力形式

N M
s t
u_1 v_1 w_1
...
u_M v_M w_M

制約

$2 \le N \le 300$
$1 \le M \le 2000$
$1 \le s,t \le N,\ s\ne t$
$1 \le w_i \le 10^6$
多重辺あり

入出力例

入力例1

4 4
1 4
1 2 1
1 3 2
2 4 2
3 4 1

出力例1

6

パス$1\to2\to4$（長さ3）とパス$1\to3\to4$（長さ3）は辺を共有せず合計6。

入力例2

3 2
1 3
1 2 3
2 3 4

出力例2

-1

$1\to3$への単純パスは$1\to2\to3$の1本しかなく、辺素な2本目が作れない。

概念図: 残余グラフによるパスのキャンセル

1回目の最短路木の辺を逆向き0コストに張り替えてから2回目を探す s u x v t 1本目 (s→u) 1本目 (u→v) 1本目 (v→t) 2本目 (s→x) 2本目がu→vの逆辺(コスト0)を使って打ち消す 残余辺(v→u, コスト0)を経由することで2本のパスが辺u→vを共有しない形に再構成される

ヒント（段階的開示）

ヒント1: 方向性
1本目の最短路を求めた後、その辺を禁止してもう1本探すという素朴な方法では最適解にならないことがある。2本のパスが部分的に同じ区間を逆向きに使うことで全体が短くなるケースに注意しよう。
ヒント2: アプローチ
この問題は容量1の辺を持つグラフで$s$から$t$へ2単位の流量を最小コストで流す問題と等価。すべて非負重みなので、successive shortest augmenting path法をポテンシャル付きダイクストラで2回適用すればよい。1回目の距離$h(v)$で辺コストを$w(u,v)+h(u)-h(v)\ge0$に補正してから2回目を探す（Johnson's algorithmと同じ考え方）。
ヒント3: 誘導（コード骨格） 
h = [0]*N
total_cost = 0
flow = 0
while flow < 2:
    # ダイクストラ: 緩和コストは cost + h[u] - h[v]
    if dist[t] == INF:
        return -1
    for v in range(N):
        if dist[v] < INF:
            h[v] += dist[v]
    # 経路復元しボトルネック分だけ流す。逆辺も更新
    total_cost += bottleneck * h[t]
    flow += bottleneck
return total_cost

模範解答 (Python)

import sys
import heapq


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    s = int(data[idx]) - 1; idx += 1
    t = int(data[idx]) - 1; idx += 1

    graph = [[] for _ in range(n)]  # graph[u] = [ [v, cap, cost, rev_index], ... ]

    def add_edge(u, v, cap, cost):
        graph[u].append([v, cap, cost, len(graph[v])])
        graph[v].append([u, 0, -cost, len(graph[u]) - 1])

    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        add_edge(u, v, 1, w)

    INF = float('inf')
    h = [0] * n
    total_cost = 0
    flow = 0
    need = 2

    while flow < need:
        dist = [INF] * n
        dist[s] = 0
        prevv = [-1] * n
        preve = [-1] * n
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for i, e in enumerate(graph[u]):
                v, cap, cost, rev = e
                if cap > 0:
                    nd = d + cost + h[u] - h[v]
                    if nd < dist[v]:
                        dist[v] = nd
                        prevv[v] = u
                        preve[v] = i
                        heapq.heappush(pq, (nd, v))
        if dist[t] == INF:
            print(-1)
            return

        for v in range(n):
            if dist[v] < INF:
                h[v] += dist[v]

        v = t
        d_path = float('inf')
        while v != s:
            u = prevv[v]
            i = preve[v]
            d_path = min(d_path, graph[u][i][1])
            v = u

        v = t
        while v != s:
            u = prevv[v]
            i = preve[v]
            graph[u][i][1] -= d_path
            rev = graph[u][i][3]
            graph[graph[u][i][0]][rev][1] += d_path
            v = u

        flow += d_path
        total_cost += d_path * h[t]

    print(total_cost)


solve()
計算量: $O(2 \cdot M \log N)$（ダイクストラを2回・優先度付きキュー使用）。ランダム300ケースで辺素パスの全列挙による厳密解と一致することを確認済み。

Step-by-Step 解説

1問題をフローに帰着する
容量1の辺だけを使って2単位の流量を流す最小費用流に帰着。2単位流せなければ$-1$。
2ポテンシャル付きダイクストラ
1回目の距離$h$で辺コストを$w(u,v)+h(u)-h(v)$に補正し、負コストの残余辺があっても非負を保ってダイクストラを繰り返せる。
3Suurballeとの対応
1回目の最短路木の辺は補正後コスト0になる。2回目でその逆辺（残余辺）を辿ることは、木の辺を逆向き0コストに張り替える古典的手続きと数学的に同一。
4経路復元とコスト累積
各反復で経路上のボトルネック容量だけ流量を流し、$h(t)$更新後の値×流量を合計コストに加算する。

よくあるミス

ミス原因正しい書き方
1本目の辺を使用禁止にして2本目を探す2本のパスが一部を共有・打ち消し合う最適構造を見逃す残余グラフ（逆辺）を使うSSP法/Suurballeを用いる
2回目のダイクストラで元の重み$w$をそのまま使う残余辺は負コストになり得るためダイクストラが誤動作ポテンシャル補正した reduced cost を使う
流量2を流せない場合の判定を忘れる辺素な2本目が存在しないケースの検出漏れ各反復で`dist[t]==INF`なら直ちに`-1`
コストを補正前の距離で計算補正後の距離は実コストと異なる`h[t]`更新後の値でコストを累積する

次のステップ

  • 発展: $K$本の辺素な最短路対の合計最小コストを求める（同じSSP法を$K$回繰り返す）
  • 発展: 頂点素な2経路を求める場合、頂点分割テクニックと組み合わせる
  • 次回予告: 永続Union-Find（バージョン管理された連結性判定・二分探索による時刻特定）

自己評価

自分の回答

気づき・メモ