【競プロ】単一始点最短路問題の双対問題（牛ゲー）

はじめに

（今更ですが，）競技プログラミングを通してデータ構造とアルゴリズムについて学び直しているものです．2025 年 5 月 3 日に開催された AtCoder ABC404 の G 問題 が単一始点最短路問題の双対性に関するお題であり，忘備を兼ねてまとめておきたいと思います．

主問題

まずは単一始点最短路問題を流量モデルとして定式化します．

有向グラフ $G = (V, E)$ の各辺 $(i, j) \in E$ の重みを $w_{ij}$ とします．今，始点 $s \in V$ と終点 $t \in V$ が与えられ，「 $s$ から $t$ へ 1単位のフローを送り，コストを最小化する」という線形計画問題（LP）を考えます：

$$
\begin{align}
\min_{f} &\sum_{(i,j)\in E} w_{ij},f_{ij}\\
\text{s.t.}\quad
& \sum_{o:\,(v,o)\in E}f_{vo} - \sum_{i:\,(i,v)\in E}f_{iv} = b_v := \left\{
\begin{array}{cc}
1, & v = s, \\
0, & v\in V\setminus\{s,t\}, \\
-1, & v = t,
\end{array}
\right. \tag{P-1}\\
&f_{ij} \ge 0 \quad\forall (i,j) \in E \tag{P-2}.
\end{align} \tag{P}
$$

ここで，$f_{ij}$ は辺 $(i, j)$ に流すフローを表しています．等式制約 (P-1) では始点 $s$（終点 $t$）で合計 1 単位のフローを流し出し（吸い込み），それ以外の点 $v$ では「流入量 = 流出量」の関係を満たすことを制約しています．

ここで，$A \in \mathbb{R}^{\lvert V \rvert \times \lvert E \rvert}$ を incidence matrix とします．つまり，

$$
A_{v, (i, j)} =
\left\{
\begin{array}[cc]
+1, & v = i, \\
-1, & v = j, \\
0, & \text{otherwise}.
\end{array}
\right.
$$
で定義します．

$A$ を用いると主問題の等式制約 (P-1) は

$$
A f = b
$$

と表すことができ，主問題 (P) も

$$
\begin{align}
\min_{f} &　w^{\top} f\\
\text{s.t.}\quad
& Af = b \\
&f \ge 0
\end{align} \tag{$\text{P}^{\prime}$}
$$

にまとめられます．ここで，$w, f \in \mathbb{R}^{\lvert E \rvert}$，$b \in \mathbb{R}^{\lvert V \rvert}$，$f\ge 0$ は $f$ の全ての要素が非負であることを意味しています．

双対問題

主問題の等式制約 ($\text{P}^{\prime}$) の双対問題は双対変数 $y \in \mathbb{R}^{\lvert V \rvert}$ を用いて，

$$
\begin{align}
\max_{y} &　b^{\top} y \\
\text{s.t.}\quad
& A^{\top} y \le w
\end{align} \tag{$\text{D}^{\prime}$}
$$

となり，ベクトル表記から各成分を用いて書き下すと，

$$
\begin{align}
\max &　y_s - y_t \\
\text{s.t.}\quad
& y_i - y_j \le w_{ij}, \quad \forall (i, j) \in E
\end{align} \tag{D}
$$

となります．この双対問題 (D) は

$$
y \mapsto y + c 1_{\lvert V \rvert} \quad (c\in \mathbb{R})
$$

というゲージ変換に対して不変であるので，

$$
y_s = 0
$$

と始点を固定して解くこともできます．また，$d_v = - y_v$ と変数を置きなおすと，

$$
\begin{align}
\max &　d_t - d_s \\
\text{s.t.}\quad
& d_j - d_i \le w_{ij}, \quad \forall (i, j) \in E
\end{align} \tag{$\text{D}^{\circ}$}
$$

となり，所謂「牛ゲー」と呼ばれる問題に帰着します¹．

強双対性² より，主問題 ($\text{P}^{\prime}$) と双対問題 ($\text{D}^{\prime}$) のどちらにも実行可能解が存在するのであれば，それぞれ最適解 $f^\ast, y^{\ast}$ が存在し，

$$
w^{\top} f^{\ast} = b^{\top} y^{\ast}
$$

が成り立ちます．つまり，「実数重み付き有向グラフ上の単一始点最短路問題」と「牛ゲー」それぞれの最適時の目的関数の値は一致するので，「牛ゲー」を「実数重み付き有向グラフ上の単一始点最短路問題」と見做して解くことができます．

例題をといてみる

問題

ABC404 の G 問題を例題として解いていきます．

整数 $N$ と長さ $M$ の正整数列 $L = (L_1, \ldots, L_M), R = (R_1, \ldots, R_M), S = (S_1, \ldots, S_M)$ が与えられます．
このとき長さ $N$ の正整数列 $A = (A_1, \ldots, A_N)$ のうち，以下の条件を満たすものが存在するか判定し，存在する場合 $A$ の総和の最小値を求めよ．
$$
\text{条件: } \sum_{j = L_i}^{R_i} A_i = S_i \quad \forall i \in \{ 1. \ldots, M\}
$$

解答例

$A_0 = 0$ として，$B_k = \sum_{j = 0}^{k} A_k$ とします．すると，与えられた問題は次のように整理されます．

$$
\begin{align}
\max\; & B_0 - B_N\\
\text{s.t.}\quad
& B_{R_i} - B_{L_i - 1} \le S_i \quad \forall i \in \{ 1. \ldots, M\}, \\
& B_{L_i - 1} - B_{R_i} \le - S_i \quad \forall i \in \{ 1. \ldots, M\}, \\
& B_{k - 1} - B_{k} \le - 1 \quad \forall k \in \{ 1. \ldots, N\}, \\
\end{align}
$$

これを双対問題 (D) と比較すると，$V = \{0, 1, \ldots, N\}$ を用意して，

1. 頂点 $R_i$ から頂点 $L_i - 1$ に重み $S_i$ の辺を張る
2. 頂点 $L_i - 1$ から頂点 $R_i$ に重み $- S_i$ の辺を張る
3. 頂点 $k - 1$ から頂点 $k$ に重み $-1$ の辺を張る

ことによってグラフを作成し，Bellman-Ford アルゴリズムによって始点 0 から終点 $N$ までの最短路を導く．最短路が存在すれば，その最短路にかかるコストが $B_0 - B_N$ に一致するので，最終的な解はコストを $-1$ 倍したものとなる．

以下が python による実装例になります．（TLE を防ぐために途中で Early Stopping を入れています．）

import sys

input = sys.stdin.readline
INF = int(1e18)


def main():
    N, M = map(int, input().split())
    edges: list[list[int]] = []
    for _ in range(M):
        l, r, s = map(int, input().split())
        edges.append([l - 1, r, -s])
        edges.append([r, l - 1, s])
    for i in range(N):
        edges.append([i, i + 1, -1])

    # Bellman-Ford Algorithm
    dist = [INF] * (N + 1)
    dist[0] = 0
    for _ in range(N):
        updated = False  # For early stopping
        for u, v, w in edges:
            if dist[u] != INF and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] != INF and dist[v] > dist[u] + w:
            print(-1)
            return

    print(-dist[N])


if __name__ == "__main__":
    main()

まとめ

今回は，「実数重み付き有向グラフ上の単一始点最短路問題」と「牛ゲー」が互いに双対関係であることを確認しました．「牛ゲー」から適切なグラフを素早く構築できるかが競プロにおいては大事になってくるなと痛感した次第です．

1. 「牛ゲー」の名前の由来は POJ の問題 に出現する牛が由来らしいです．牛ゲーの詳細については解説 を参考にしてください． ↩

2. 「数理最適化入門 (1)：線形計画（宮本）」 などを参考にしました． ↩