結論

$\displaystyle{ \phi }$ をポテンシャルとして $\displaystyle{ \phi[v] - \phi[s] }$ の最大値を求める問題は、 $\displaystyle{ s }$ を始点として $\displaystyle{ v }$ への最短路長を求める問題の双対問題（dual problem）となる。

前提

線形計画問題（以下 LP ）:

$\displaystyle{ m \times n }$ の行列 $\displaystyle{ A }$
$\displaystyle{ m }$ 次元のベクタ $\displaystyle{ b }$
$\displaystyle{ n }$ 次元のベクタ $\displaystyle{ c }$

が与えられ、 $\displaystyle{ Ax \le b }$ の制約下において、 objective function $\displaystyle{ \sum_{i=1}^{n} c_i x_i }$ を最大化する $\displaystyle{ n }$ 次元のベクタ $\displaystyle{ x }$ を求める問題。

ポテンシャル

以下のグラフを LP で定式化することを考える。

それぞれの辺がどの頂点を繋いでいるのかを表現した $\displaystyle{ |E| \times |V| }$ 行列 $\displaystyle{ A }$ を用意する。辺 $\displaystyle{ (v_i, v_j) }$ について $\displaystyle{ i }$ 列 $\displaystyle{ =-1 }$ , $\displaystyle{ j }$ 列 $\displaystyle{ =1 }$ , それ以外の要素を $\displaystyle{ 0 }$ 埋めして表現する。

さらに、

それぞれの頂点への到達コストを、 $\displaystyle{ |V| }$ 次元のベクタ $\displaystyle{ x }$
それぞれの辺のコスト $\displaystyle{ w(u, v) }$ を、 $\displaystyle{ |E| }$ 次元のベクタ $\displaystyle{ b }$

とする。

これらを元として、このグラフは、次のように定式化することができる。

分解すると次のようになる。

$\displaystyle{ x_1 - x_2 \le 0, }$

$\displaystyle{ x_1 - x_5 \le -1, }$

$\displaystyle{ x_2 - x_5 \le 1, }$

$\displaystyle{ x_3 - x_1 \le 5, }$

$\displaystyle{ x_4 - x_1 \le 4, }$

$\displaystyle{ x_4 - x_3 \le -1, }$

$\displaystyle{ x_5 - x_3 \le -3, }$

$\displaystyle{ x_5 - x_4 \le -3, }$

この制約は何を意味するか。

たとえば、 $\displaystyle{ x_5 - x_4 \le -3 }$ を例とすると、「 $\displaystyle{ v_5 }$ への到達コスト $\displaystyle{ x_5 }$ は、 $\displaystyle{ x_4 }$ に、 $\displaystyle{ v_4 }$ から $\displaystyle{ v_5 }$ への経路のコストを足し合わせたもの $\displaystyle{ x_4 + w(v_4, v_5) }$ 以下になる」ことを意味する。

$\displaystyle{ Ax \le b }$ の制約を満たす $\displaystyle{ x }$ の解の1つに、 $\displaystyle{ x = (-5, -3, 0, -1, -4) }$ が考えられる。

他にも、 $\displaystyle{ x = (0, 2, 5, 4, 1) }$ など、複数の解が考えられるだろう。

この、 $\displaystyle{ Ax \le b }$ の制約を満たす解の組み合わせ、具体的には

任意の $\displaystyle{ u,v \in V }$ に対して、 $\displaystyle{ \phi [v] - \phi [u] \le w(u,v) }$ を満たすような $\displaystyle{ \phi }$

のことを ポテンシャル と呼ぶ。

参考にした書籍でわかりやすかった説明を引用する。

各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてありうるものをポテンシャルと呼びます。より正確には、各頂点 $\displaystyle{ v }$ に対して値 $\displaystyle{ \phi[v] }$ が定まっているとき、任意の辺 $\displaystyle{ e=(u,v) }$ に対して、 $\displaystyle{ \phi[v] - \phi[u] \le w(u,v) }$ を満たすような $\displaystyle{ \phi }$ のことをポテンシャルと呼びます。

最短路問題とポテンシャル

実は、点 $\displaystyle{ u }$ から点 $\displaystyle{ v }$ への最短路（最小コストで到達できる経路）を求める問題は、 $\displaystyle{ \phi[v] - \phi[u] }$ の最大値を求める問題の双対問題（dual problem）となっている。

すなわち、以下の命題が成立する。

頂点 $\displaystyle{ u }$ から頂点 $\displaystyle{ v }$ へ到達可能な時、 $\displaystyle{ u }$ から $\displaystyle{ v }$ への最小コスト $\displaystyle{ = max(\phi[v] - \phi[u]) }$