最短経路問題の双対問題

まずは次の問題を考えます。

---

問題：
\(N+1\) 個の変数 \(d_0,\dots,d_{N}\) を、次の条件を満たすように定める 。

• \(d_0=0\)
• 全ての \(i=1,\dots,M\) について \(d_{u_i}-d_{v_i}\leq w_i\)

条件を満たすことが可能か判定し、可能なら \(d_N\) の最大値を求めよ。

---

この問題は最短経路問題をLP(整数計画問題)として定式化したものの双対問題であることが知られています。LP双対に関する強双対性から、この問題は次の問題の答えと等しくなります。

---

双対問題：
頂点に \(0\) から \(N\) の番号がついた \(N+1\) の有向グラフがある。\(M\) 本の辺があり、\(i\) 番目の辺は頂点 \(d_{v_i}\) から頂点 \(d_{u_i}\) への距離 \(w_i\) の辺である。このグラフに負閉路があるかどうか判定せよ。また、頂点 \(0\) から頂点 \(N\) へ到達可能かどうか判定し、可能なら最短距離を求めよ。

---

この双対問題はベルマンフォード法により \(O(NM)\) で解を求めることができます。

1次元の場合

元の問題の1次元の場合を考えます。

---

問題：
数直線上に \(N\) 個の点 \(x_1,\ldots,x_N\) を以下の全ての条件を満たすように配置する。

• 各 \(i=1,\ldots,N\) について、点 \(x_i\) と点 \(a_i\) の距離が \(d_i\) 以下である
• 各 \(j=1,\ldots,M\) について、点 \(x_{u_j}\) と点 \(x_{v_j}\) の距離が \(e_j\) 以下である

以上の条件を満たすような \(N\) 個の点の配置が存在するか判定し、存在するならば、原点 \(0\) と点 \(x_N\) の距離の最大値を求めよ。

---

問題の条件は \(x_0=0\) となる変数を追加することで、次のように変換できます。

• 各 \(i=1,\ldots,N\) について、\(x_0-x_i \leq -a_i+d_i\) かつ \(x_i-x_0 \leq a_i+d_i\) である。
• 各 \(j=1,\ldots,M\) について、\(x_{u_j} - x_{v_j} \leq e_j\) かつ \(x_{v_j} - x_{u_j} \leq e_j\) である。

よってこの問題は最初に述べた最短経路問題の双対問題であり、ベルマンフォード法により \(O(NM)\) で解くことができます。

2次元の場合

元の問題を考えます。\((x,y)\mapsto(x+y,x-y)\) により座標系の変換を行います。変換前の座標系におけるマンハッタン距離は、変換後の座標系におけるチェビシェフ距離になります。点 \((p_1,q_1)\) 点 \((p_2,q_2)\) のチェビシェフ距離とは \(\max(|p_1-p_2|,|q_1-q_2|)\) です。

この変換により2つの座標軸について独立に考えることができるようになるため、1次元の問題に帰着されました。
座標の絶対値の最大化は、座標の最大化と座標の最小化の2つの問題を解けばよく、後者は座標軸を反転させることで最大化問題に帰着できます。