ジョンソン法 (グラフ理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/03 06:18 UTC 版)
| クラス | （重み付き）最短経路問題 | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| データ構造 | グラフ | ||||||||||||||
| 最悪計算時間 | 
左のグラフでは二つの負の重みを持つ辺があるが、負閉路は含まれていない。中央のグラフでは新たに頂点 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 は以下のように表される:
|
||||||||||||||
| 非線形（制約付き） |
|
||||||||||||||
| 凸最適化 |
|
||||||||||||||
| 組合せ最適化 |
|
||||||||||||||
| メタヒューリスティクス | |||||||||||||||
- ジョンソン法_(グラフ理論)のページへのリンク
