スケジューリング問題に対するアルゴリズムについては「ジョンソン法 （英語版 ）
ジョンソン法 (グラフ理論) クラス
（重み付き）最短経路問題 データ構造
グラフ 最悪計算時間
O
(
|
V
|
2
log
|
V
|
+
|
V
|
|
E
|
)
{\displaystyle O(|V|^{2}\log |V|+|V||E|)}
ジョンソン法 （ジョンソンほう、英 : Johnson's algorithm ）とは、重み付き有向グラフでの全点対の最短経路 を求める解法である。重みに負の値 を含んでいても動作するが、グラフに負閉路 を含む問題には適用することができない。ベルマン・フォード法 を用いて負の重みを持つグラフを変換し、ダイクストラ法 を用いて変換後のグラフの最短経路を求める[ 1] [ 2] ドナルド・ジョンソン （英語版 ） [ 3]
再重み付けを行う同様のアルゴリズムとしてエドモンズ・カープの最小費用流問題 に対する逐次最短路法や[ 4] スアバレ法 （英語版 ） [ 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 )
再重みづけされたグラフでは全点対 s ,t 間に h (s ) − h (t )p を s-t 間の路としたとき、再重み付けグラフでの重み 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
)
)
.
{\displaystyle \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
)
{\displaystyle +h(p_{i})}
−
h
(
p
i
)
{\displaystyle -h(p_{i})}
(
w
(
s
,
p
1
)
+
w
(
p
1
,
p
2
)
+
⋯
+
w
(
p
n
,
t
)
)
+
h
(
s
)
−
h
(
t
)
{\displaystyle \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
|
)
{\displaystyle O(|V|^{2}\log |V|+|V||E|)}
O
(
|
V
|
|
E
|
)
{\displaystyle O(|V||E|)}
O
(
|
V
|
log
|
V
|
+
|
E
|
)
{\displaystyle O(|V|\log |V|+|E|)}
|
V
|
{\displaystyle |V|}
疎グラフ （英語版 ）
O
(
|
V
|
3
)
{\displaystyle O(|V|^{3})}
ワーシャル・フロイド法 より高速に動作する[ 1]
^ a b c d Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introduction to Algorithms ISBN 978-0-262-03293-3
^ a b Black, Paul E. (2004), “Johnson's Algorithm” , Dictionary of Algorithms and Data Structures , National Institute of Standards and Technology , https://xlinux.nist.gov/dads/HTML/johnsonsAlgorithm.html
^ Johnson, Donald B. (1977), “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM 24 (1): 1–13, doi :10.1145/321992.321993 ^ Edmonds, J.; Karp, Richard M. (1972), “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”, Journal of the ACM 19 (2): 248–264, doi :10.1145/321694.321699 ^ Suurballe, J. W. (1974), “Disjoint paths in a network”, Networks 14 (2): 125–145, doi :10.1002/net.3230040204
