前置き

夏休みだ〜！！ということで気合いを入れて蟻本を読み進めていたら、2章のグラフのところで牛ゲーと呼ばれる問題と出会いました。

牛ゲーとは数列 $d_i$ について

\begin{align} d_j - d_i \leq c_{ij}(const) \tag{1} \end{align}

という形でのみ表される条件がたくさんあるとき、ある $g, s$ について $d_g - d_s$ の最小値を求めようみたいな問題のようです。蟻本に載っているPOJ3169が牛の問題だからこの名前がついてるっぽいですね。例えばこういうやつです。

蟻本ではこの問題を、上のような条件を持つ各 $i, j$ について辺 $i \to j$ の重みを $c_{ij}$ とした有向グラフを考えた時に、頂点 $s$ から頂点 $g$ に向かう最短距離を求める、というものに帰着していました。確かにそう最短路に帰着できそうとは思いつつも、なんとなく腑に落ちなかったので少し自分なりに考えてみました。

証明(?)

数列 $d_i$ が有向グラフ $G$ 上での頂点 $s$ から各頂点 $i$ への最短距離を表しているという仮定の元で、条件として新たに(1)式を追加することと、有向グラフ $G$ に $i \to j$ へと向かう重みが $c_{ij}$ の辺を書き加えることとが等価であることを示せば良さそうですね。

まず(1) の条件を追加するような辺の書き加え方を考える。 $d_i$ というのは最短距離を表すので、満たすべき関係式は

\begin{align} d_i \leq (sからiに向かう任意の経路の長さ) \end{align}

であり、この他の制約はない。

したがって(1)式、つまり

\begin{align} d_j \leq d_i + c_{ij}(const) \tag{1} \end{align}

が成立するとすれば、それは $s \to j$ へ向かう経路の中に経路長が $d_i + c_{ij}$ であるものが存在する時である。また辺の追加の過程で $d_i$ の値は変わりうるので、(1)の条件を追加する方法は $i \to j$ と向かう長さ $c_{ij}$ の経路を書き加えるという他ない。