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

ジョンソン法の概要

ジョンソン法（Johnson's algorithm）は、重み付き有向グラフにおける全点対の最短経路を効率的に求めるためのアルゴリズムです。この方法は、特に負の重みを持つ辺が存在するグラフにおいても適用でき、ただし、負の閉路が存在する場合には使用できません。1977年にドナルド・ジョンソンによって提案されたことからその名が付けられました。

ジョンソン法は、主に以下の手順から構成されています。まず、各頂点に接続する新たな頂点を追加し、この頂点からの重みをゼロとします。この頂点を用いてベルマン・フォード法を適用し、元のグラフの各頂点までの最短経路を計算します。その後、得られた結果を用いて元のグラフの重みを再計算し、ダイクストラ法を利用して最短経路を求めるという流れになります。

アルゴリズムの手順

1. 新たな頂点の追加: 新しい頂点 q を追加し、全ての元の頂点と q を結ぶ辺の重みをゼロに設定します。
2. ベルマン・フォード法の適用: 頂点 q から各頂点への最短距離 h(v) を計算します。もし負の閉路が検出された場合、アルゴリズムを終了します。
3. 重みの再計算: 元のグラフの各辺の重み w(u, v) を、式 w(u, v) + h(u) - h(v) により再計算します。
4. 頂点 q の削除: 最後に頂点 q を削除し、ダイクストラ法を用いて再重み付けされたグラフ上で元の各頂点との最短経路を求めます。

この手法により、重みが非負の新しいグラフが作成されます。このグラフにおいて、各頂点間の最短経路をダイクストラ法で計算することが可能となります。

具体的な例

例えば、AとBの間、およびBとCの間に負の重みを持つ辺がある場合を考えます。この際、qを追加し、再重み付けを行うことで、全ての辺の重みを非負とすることができます。再重み付け後のグラフでも、最短経路の辺の順序は維持されるため、ダイクストラ法により問題なく計算が行えます。

アルゴリズムの妥当性

ジョンソン法の重要な特性は、再重み付けされた場合でも元のグラフにおける最短路の性質が保持されることです。これは、重みの差分として h(s) - h(t) を各 s-t 路に加えることによって証明されます。この手法により、最適性が保たれるため、効率的なアルゴリズムとなっています。

時間計算量

ジョンソン法の時間計算量は、ダイクストラ法にフィボナッチヒープを用いることで O(|V|^2 log |V| + |V||E|) となります。この計算量は、アルゴリズムの各ステップで必要な計算量に基づいています。疎グラフの場合、ワーシャル・フロイド法よりもはるかに早く、全点対の最短経路を求めることができます。

このように、ジョンソン法は特に重み付き有向グラフにおいて、計算効率と柔軟性を兼ね備えた強力なアルゴリズムとして幅広く利用されています。

もう一度検索