ジョンソン法 (グラフ理論)

ジョンソン法 (グラフ理論)
クラス	（重み付き）最短経路問題
データ構造	グラフ
最悪計算時間

ジョンソン法（ジョンソンほう、英: Johnson's algorithm）とは、重み付き有向グラフでの全点対の最短経路を求める解法である。重みに負の値を含んでいても動作するが、グラフに負閉路を含む問題には適用することができない。ベルマン・フォード法を用いて負の重みを持つグラフを変換し、ダイクストラ法を用いて変換後のグラフの最短経路を求める^[1]^[2]。1977年、ドナルド・ジョンソン（英語版）により提案されたことが名前に由来する^[3]。

再重み付けを行う同様のアルゴリズムとしてエドモンズ・カープの最小費用流問題（英語版）に対する逐次最短路法や^[4]、重みが非負のグラフ上における2頂点間の独立した2つの最短経路を求めるスアバレ法（英語版）が挙げられる^[5]。

アルゴリズムの説明

ジョンソン法は以下の手順により構成されている^[1]^[2]:

初めにグラフに各頂点に接続し、枝の重みがゼロの頂点 $q$ を新たに追加する。
続いてベルマン・フォード法を用いて、頂点 $q$ から頂点 $v$ への最短路を頂点 $q$ から頂点 $v$ の重み $h (v)$ とする。もし負閉路が検出されたならば、アルゴリズムは終了する。
加えてベルマン・フォード法により元のグラフの辺を最重み付けする: 頂点 $u$ から頂点 $v$ の辺の距離 $w(u, v)$ を式 $w (u, v) + h (u) - h (v)$ によって再計算する。
最後に頂点 $q$ を削除し、ダイクストラ法を用いて最重み付けグラフ上で頂点 $s$ から残りの各頂点に対する最短路を求める。再びダイクストラ法により $h (v) - h (u)$ を求めて元のグラフでの距離 $D$ ( $u$ , $v$ ) を計算する。

具体例

以下ではジョンソン法の最初の3ステップについて説明する。

左のグラフでは二つの負の重みを持つ辺があるが、負閉路は含まれていない。中央のグラフでは新たに頂点 $q$ を付け加え、ベルマンフォード法を用いて頂点 $q$ から各頂点への最短路の値を計算し、これを頂点 $q$ から各頂点へ接続する辺の重み $h (v)$ と再重み付けする。再重み付けにより頂点 $q$ から各頂点へ接続する辺の重みはゼロであることから、グラフの重みはすべて非負の値をとる。右のグラフは各辺の重み $w(u, v)$ を $w (u, v) + h (u) - h (v)$ によって求めた再重み付けグラフを表している。この再重み付けグラフは元のグラフとは異なってすべての辺が非負の重みであるが、再重み付けグラフ上の2頂点間の最短路で通る辺の順序は元のグラフ上における最短路で通る最短路の辺の順序と同一である。したがってダイクストラ法により再重み付けグラフ上で各2点間の最短路をダイクストラ法によって求める。

アルゴリズムの妥当性

再重みづけされたグラフでは全点対 $s$ , $t$ 間に $h (s) - h (t)$ を加える。これは $p$ を $s-t$ 間の路としたとき、再重み付けグラフでの重み W は以下のように表される:

$\left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).$

上記の括弧内の $+h(p_{i})$ はすべて $-h(p_{i})$ によって差し引かれるため、括弧内は以下ように表される:

$\left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)$

ただし、括弧内は元のグラフにおける路 p の重みの和を表す。

このことから再重み付けによってすべての $s-t$ 間の路の重みに同じ値 $h (s) - h (t)$ が加わるため、ある路が元のグラフにおいての最短路であることと、再重み付けグラフでの最短路であることは等価である。また q から各頂点に接続する辺の重みはゼロであることから、再重み付けグラフにおいても q から各頂点への最短路の値が必ずゼロになる。それゆえ負の辺は存在し得ない。仮に再重み付けグラフ上で辺 u-v の重みが負であるとすると q から u への重みゼロの辺と組み合わせることで q から v への負の重みの辺ができることになり、すべての頂点が q からの重みがゼロであるという事実に違反する。このことから、再重み付けグラフには負の辺が存在しないことが保証されるのでダイクストラ法により最短路を求めることができる。元のグラフの最短路は再重み付けグラフに対してダイクストラ法を用いて最短路求め、再重み付けによる重みの変換を逆にして適用することで求まる^[1]。

分析

ジョンソン法の時間計算量はフィボナッチヒープを用いたダイクストラ法によって計算量 $O(|V|^{2}\log |V|+|V||E|)$ で動作する。これはベルマン・フォード法を使用するステップで計算量 $O(|V||E|)$ がかかり、計算量 $O(|V|\log |V|+|E|)$ のダイクストラ法をおおよそ $|V|$ 回使用することから求まる。また、疎グラフ（英語版）上では全頂点間グラフを計算量 $O(|V|^{3})$ で解くワーシャル・フロイド法より高速に動作する^[1]。