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

ジョンソン法（ジョンソンほう、テンプレート:Lang-en-short）とは、重み付き有向グラフでの全点対の最短経路を求める解法である。重みに負の値を含んでいても動作するが、グラフに負閉路を含む問題には適用することができない。ベルマン・フォード法を用いて負の重みを持つグラフを変換し、ダイクストラ法を用いて変換後のグラフの最短経路を求める。1977年、テンプレート:仮リンクにより提案されたことが名前に由来する。

再重み付けを行う同様のアルゴリズムとしてエドモンズ・カープのテンプレート:仮リンクに対する逐次最短路法や、重みが非負のグラフ上における2頂点間の独立した2つの最短経路を求めるテンプレート:仮リンクが挙げられる。

アルゴリズムの説明

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

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

具体例

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

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

アルゴリズムの妥当性

再重みづけされたグラフでは全点対 テンプレート:Mvar,テンプレート:Mvar 間に テンプレート:Math を加える。これは テンプレート:Mvar を テンプレート:Math 間の路としたとき、再重み付けグラフでの重み W は以下のように表される:

$$(w(s,p_1)+h(s)-h(p_1))+(w(p_1,p_2)+h(p_1)-h(p_2))+...+(w(p_n,t)+h(p_n)-h(t)).$$

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

$$(w(s,p_1)+w(p_1,p_2)+\cdots +w(p_n,t))+h(s)-h(t)$$

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

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

分析

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

外部リンク

• Boost: All Pairs Shortest Paths