1. 差分制約系の定義と解法

以下のような線形計画問題を差分制約系という。

• maximize $y_N - y_1$
• subject to
  • $y_{v_i} - y_{u_i} \leq c_i$ ( $i=1,2,\ldots, M$ )

同じことであるが、実行可能ポテンシャルを使うと、差分制約系は以下のように書ける。

• maximize $\varphi(t) - \varphi(s)$
• subject to
  • $\varphi\colon V \to \mathbb{R}$ がコスト $c\colon V^2 \to \mathbb{R}\cup\{+\infty\}$ に対する実行可能ポテンシャル。
    • つまり任意の頂点 $x, y$ に対して $\varphi(y)-\varphi(x) \leq c(x,y)$

（ポテンシャルについてはポテンシャル を参照）

差分制約系の解は以下のような最短路問題の最短路長と一致していることが示せる。

• $i$ 番目の辺が $u_i \to v_i$ でコストが $c_i$ で与えられているグラフが与えられる。頂点 $1$ から頂点 $N$ までの最短路を求める
• 頂点が $V$、辺のコストが $c\colon V^2 \to \mathbb{R}\cup \{+\infty\}$ でグラフが与えられる。頂点 $s$ から頂点 $t$ までの最短路を求める

つまり、最短路問題を解けば、差分制約系も解ける。

直感的には、コストの大きさの分の長さを持つ紐で各頂点を結び、始点と終点を引っ張るのをイメージすると、差分不等式系の解が最短路長になることがわかりやすい

（逆辺を持つ場合や負辺を持つ場合はこのイメージでは理解が難しい？）