2022/01/15 修正・有向グラフの図追加

初めに

AtCoderの問題で牛ゲーが出たので、まとめておきます。数学的に厳密でない部分や、誤りを含む場合もありますのでご了承ください。

牛ゲーとは

以下の2つの問題があります。


という「2つの値の差分についての制約」のみからなる制約の元で、と各の差を最大化する線形計画問題

重みつき有向グラフについて、頂点から頂点にコストの有向辺があることをと表現する。


という辺がある重みつき有向グラフについて、始点から各頂点への最小コストを求める最短経路問題

この2つから得られる $d_{v_i}-d_s$ の最大値と、始点 $d_s$ から頂点 $v_i$ への最小コスト $d_{v_i}$ が同じになります。

従って、

2つの値の差分についての制約のみからなる
値を最大化する

という条件を満たす問題は、最短経路問題に帰着して解くことができます。

計算量は、 $w_i\lt 0$ を含むならBellman-Ford法によって、 $O(|V||E|)$ 、非負整数のみならDijkstra法によって、 $O(|E|log|V|)$ です。

最大値と最短経路

最短経路問題の最小コストが、線形計画問題の最大値を与えるというのがよくわかりませんでした。
この点について考察してみます。

例として、以下の有向辺を持つ有向グラフを考えます。

f:id:geam1113:20220115060606p:plain — 有向グラフ

$d_1 = 0$ とし、 $d_2 = 1$ までが求まっているとして、 $d_3$ を求めます。

有向辺を差分の制約とみなします。具体的には、
2から3への重み1の有向辺は、 $d_3 - d_2 \leq 1$
1から3への重み3の有向辺は、 $d_3 - d_1 \leq 3$
となります。
よって、条件は $d_3 \leq 2$ かつ $d_3 \leq 3$ となり、最終的に右辺が小さい方の
$d_3 \leq 2$ という条件のみとなります。
この時の右辺は、最短経路問題における最小コストであると言えます。