最短経路問題のソースを表示

[[グラフ理論]]における'''最短経路問題'''（さいたんけいろもんだい、{{lang-en-short|shortest path problem}}）とは、重み付き[[グラフ理論|グラフ]]の与えられた2つの[[グラフ理論|ノード]]間を結ぶ[[グラフ理論|経路]]の中で、重みが最小の[[道 (グラフ理論)|経路]]を求める[[最適化問題]]である。

== 種類 ==
; 2頂点対最短経路問題
: 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。
; 単一始点最短経路問題 (SSSP：Single Source Shortest Path)
: 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解く[[アルゴリズム]]としては、[[ダイクストラ法]]や[[ベルマン-フォード法]]がよく知られている。
; <nowiki>全点対最短経路問題 (APSP : All Pair Shortest Path)</nowiki>
: グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解く[[アルゴリズム]]としては、[[ワーシャル-フロイド法]]が知られている。

このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。

== 単一始点最短経路問題 ==
===辺の重みなし有向グラフ===
{| class=wikitable
! アルゴリズム !! 計算量 !! 作者
|-
| [[幅優先探索]] || <math>O(E)</math> ||
|}

===辺の重みが非負値の有向グラフ===
{| class=wikitable
! アルゴリズム !! 計算量 !! 作者
|-
| || <math>O(V^2 EL)</math> || {{harvnb|Ford|1956}}
|-
| [[ベルマン-フォード法]] || <math>O(VE)</math> || {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
|-
| || <math>O(V^2 \log{V})</math> || {{harvnb|Dantzig|1958}}, {{harvnb|Dantzig|1960}}, Minty (cf. {{harvnb|Pollack|Wiebenson|1960}}), {{harvnb|Whiting|Hillier|1960}}
|-
| [[ダイクストラ法]]（リスト） || <math>O(V^2)</math> || {{harvnb|Leyzorek|Gray|Johnson|Ladew|1957}}, {{harvnb|Dijkstra|1959}}
|-
| ダイクストラ法（修正[[二分ヒープ]]） || <math>O((E+V) \log{V})</math> ||
|- 
| . . . || . . . || . . .
|-
| ダイクストラ法（[[フィボナッチヒープ]]） || <math>O(E+V \log{V})</math> || {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}
|-
| || <math>O(E \log{\log{L}})</math> || {{harvnb|Johnson|1982}}, {{harvnb|Karlsson|Poblete|1983}}
|-
| Gabow 法 || <math>O(E \log{\frac{E}{V}} L)</math> || {{harvnb|Gabow|1983b}}, {{harvnb|Gabow|1985b}}
|-
| || <math>O(E+V \sqrt{\log{L}})</math> || {{harvnb|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}
|}

===辺の重みが任意の実数の有向グラフ===
{| class=wikitable
! アルゴリズム !! 計算量 !! 作者
|-
| [[ベルマン-フォード法]] || <math>O(VE)</math> || {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
|}

== 漸化式 ==
最短経路の距離は部分構造最適性が成立しており、下記漸化式が成立する。証明は『アルゴリズムイントロダクション』（ISBN 978-4764904088）などを参照。
:<math>V</math> が頂点、<math>E</math> が辺、<math>c(s, v)</math> が辺の重み、<math>\mathrm{dist}(s, v)</math> が最短経路の距離。<math>s, v, w \in V</math>。<math>w \ne s</math>。
:<math>\mathrm{dist}(s, s) = 0</math> とおく。
:<math>\mathrm{dist}(s, w) = \min \{ \mathrm{dist}(s, v) + c(v, w) \mid (v, w) \in E \}</math> が成立する。
単一始点の場合 <math>c(s, v) = 1</math> なら[[幅優先探索]]が、<math>c(s, v) \ge 0</math> なら[[ダイクストラ法]]が、そうでないなら[[ベルマン-フォード法]]が使える。

== ヒューリスティックスの併用 ==
辺の重みが非負値の2頂点対最短経路問題で、最短経路の距離の下限値が分かっている場合は[[A*]]を使うと、[[ダイクストラ法]]よりも速く求まる。

== 応用 ==
最短経路問題の身近な応用例には、鉄道の経路案内（[[駅すぱあと]]、[[駅探]]、[[NAVITIME]]など）がある。駅をノードとし、駅と駅の所要時間を重みとしたエッジとして、鉄道線路をグラフ化して最短経路を求めている。

== 類似問題 ==
=== 最長単純道 ===
最短経路とは逆の問題で、最長[[道 (グラフ理論)|単純道]]問題もある。最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立しておらず、[[貪欲法]]などで解くことが出来ない。辺の重みなしであっても、[[NP完全問題]]である。

=== 最短閉路 ===
* [[巡回セールスマン問題]] - グラフ内の全頂点を通り、始点に帰ってくる最短閉路を求める問題。[[NP困難]]であることが知られている。
* [[中国人郵便配達問題]] - グラフ内の全ての辺を1回以上通り、始点に帰ってくる最短閉路を求める問題。

==参考文献==
{{refbegin}}
*{{cite journal |last2=Mehlhorn |first2=Kurt |last3=Orlin |first3=James |last4=Tarjan |first4=Robert E. |date=April 1990 |title=Faster algorithms for the shortest path problem |url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA194031 |journal=Journal of the ACM |publisher=ACM |volume=37 |issue=2 |pages=213–223 |ref=harv |last1=Ahuja |first1=Ravindra K. |author4link=Robert Tarjan |doi=10.1145/77600.77615|hdl=1721.1/47994 |s2cid=5499589 |hdl-access=free }}
* {{cite journal |last=Bellman |first=Richard |year=1958 |title=On a routing problem |journal=Quarterly of Applied Mathematics |volume=16 |issue= |pages=87–90 |mr=0102435 |ref=harv|authorlink=Richard Bellman |doi=10.1090/qam/102435|doi-access=free }}
*{{cite journal |last=Dantzig |first=G. B. |date=January 1960 |title=On the Shortest Route through a Network |journal=Management Science |volume=6 |issue=2 |pages=187–190 |ref=harv |doi=10.1287/mnsc.6.2.187}}
* {{cite book |title=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems |last2=Gray |first2=R. S. |last3=Johnson |first3=A. A. |last4=Ladew |first4=W. C. |last5=Meaker |first5=S. R., Jr. |last6=Petry |first6=R. M. |last7=Seitz |first7=R. N. |publisher=Case Institute of Technology |year=1957 |location=Cleveland, Ohio |ref=harv|last1=Leyzorek |first1=M.}}
{{refend}}

{{アルゴリズム}}
{{最適化アルゴリズム}}

{{Normdaten}}
{{DEFAULTSORT:さいたんけいろもんたい}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:組合せ最適化]]
[[Category:数学の問題]]