負辺があっても、ポテンシャルを考えることで負辺のないグラフの最短経路問題に帰着できて、ダイクストラ法が使えるケースがある。

1. パスの重みの記法を定義

頂点の集合が $V$ で与えられる単純有向グラフを考える。

各辺の移動コストが $c\colon V^2 \to \mathbb{R}\cup\{+\infty\}$ で与えられているとき、パス $P$ に沿って移動したときのコスト（パスの重み）を $\int_P c$ と書くことにする。

つまり、パス $P$ が $P = (v_0, \ldots, v_{k-1})$ と表せるとき、以下の式が成り立つとする。

$$ \displaystyle \int_P c = \sum_{i=0}^{k-2} c(v_i, v_{i+1}) $$

普通の積分と同じことが成り立つ（パスに関する線形性、コストに関する線形性）

2. ポテンシャル

$\varphi\colon V\to \mathbb{R}$ を関数とする。$\varphi'\colon V^2 \to \mathbb{R}$ を $\varphi'(x,y) = \varphi(y) - \varphi(x)$ で定める。

このとき、以下が成り立つ。

• 始点を $u$, 終点を $v$ とする2つのパス $P_1, P_2$ に対して、 $\int_{P_1} \varphi' = \int_{P_2} \varphi' = \varphi(v) - \varphi(u)$ が成り立つ。
  • つまり、パスの重みは始点と終点で決まり、経路に依存しない。
  • $\int_u^v \varphi' = \varphi(v) - \varphi(u)$ って書いてもいいかもしれない。
• $C$ を閉路としたとき、$\int_{C} \varphi' = 0$ が成り立つ

3 実行可能ポテンシャル

$\varphi\colon V\to \mathbb{R}$ を関数とする。$c\colon V^2 \to \mathbb{R}\cup \{+\infty\}$ をグラフのコスト関数とする。

$\varphi'(x,y) \leq c(x,y)$ を満たす $\varphi$ を実行可能ポテンシャルという。

実行可能ポテンシャルについて以下の性質が成り立つ。

• コスト関数が $c$ で与えられるグラフについて以下が成り立つ。

  • 「実行可能ポテンシャルが存在する」ならば「負閉路は存在しない」
  • 「負閉路は存在しない」ならば「実行可能ポテンシャルが存在する」

  つまり、以下の2つは同値

  • 実行可能ポテンシャルが存在する
  • 負閉路は存在しない

• $c_{\varphi}\colon V^2 \to \mathbb{R}\cup\{\infty\}$ を $c_\varphi = c - \varphi'$ と定義したとき、以下が成り立つ

  • $c_{\varphi}(x,y) \geq 0$ なので、$c_{\varphi}$ をコストとするグラフでの単一始点最短路問題はダイクストラ法で解ける。
  • 「コスト関数が $c$ のときの $u\to v$ 最短路」は「コスト関数が $c_\varphi$ のときの $u\to v$ 最短路」と一致する

つまり、実行可能ポテンシャルが与えられれば、負辺があってもダイクストラ法で高速に単一始点最短路問題が解ける。