最短経路問題

グラフ理論において、最短経路問題とは、グラフ内の2つの頂点（またはノード）間の経路を見つけ、その経路を構成する辺の重みの合計を最小化する問題である。^{[ 1 ]}

道路地図上の2つの交差点間の最短経路を見つける問題は、グラフにおける最短経路問題の特殊なケースとしてモデル化することができ、頂点は交差点に対応し、辺は道路区間に対応し、各区間の長さまたは距離によって重みが付けられます。^{[ 2 ]}

最短経路問題は、無向グラフ、有向グラフ、混合グラフのいずれに対しても定義できます。無向グラフの定義では、すべての辺はどちらの方向にもたどることができるとされています。有向グラフでは、連続する頂点が適切な有向辺で接続されている必要があります。^{[ 3 ]}

2 つの頂点は、両方とも共通の辺に接している場合に隣接している。無向グラフのパスは、頂点のシーケンスである。${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}$そのため${\displaystyle v_{i}}$に隣接しています${\displaystyle v_{i+1}}$のために${\displaystyle 1\leq i<n}$そのような道${\displaystyle P}$長さのパスと呼ばれる${\displaystyle n-1}$から${\displaystyle v_{1}}$に${\displaystyle v_{n}}$（${\displaystyle v_{i}}$変数であり、その番号はシーケンス内の位置に関係しており、正規のラベル付けに関係する必要はありません。）^{[ 4 ]}

させて${\displaystyle E=\{e_{i,j}\}}$どこ${\displaystyle e_{i,j}}$両方に隣接するエッジは${\displaystyle v_{i}}$そして${\displaystyle v_{j}}$実数値の重み関数が与えられた場合${\displaystyle f:E\rightarrow \mathbb {R} }$、無向（単純）グラフ${\displaystyle G}$から最短経路${\displaystyle v}$に${\displaystyle v'}$道は${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$（どこ${\displaystyle v_{1}=v}$そして${\displaystyle v_{n}=v'}$）全体的に可能な限り${\displaystyle n}$合計を最小化する${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$グラフの各エッジが単位重みまたは${\displaystyle f:E\rightarrow \{1\}}$これは、辺の数が最も少ない経路を見つけることと同等です。

この問題は、以下のバリエーションと区別するために、単一ペア最短経路問題と呼ばれることもあります。 ^{[ 5 ]}

• 単一始点最短経路問題とは、始点頂点vからグラフ内の他のすべての頂点への最短経路を見つける問題である。
• 単一目的地最短経路問題とは、有向グラフのすべての頂点から単一の目的地頂点vへの最短経路を求める問題です。これは、有向グラフの弧を反転させることで、単一始点最短経路問題に帰着させることができます。
• 全ペア最短経路問題とは、グラフ内のすべての頂点ペアv、v'の間の最短経路を見つける問題です。

これらの一般化は、関連するすべての頂点ペアに対して単一ペア最短経路アルゴリズムを実行するという単純なアプローチよりも、はるかに効率的なアルゴリズムを持っています。^{[ 6 ]}

この問題とその派生問題を解くための、よく知られたアルゴリズムがいくつか存在する。

• ダイクストラ法は、非負のエッジ重みのみを持つ単一始点最短経路問題を解決する。
• ベルマン・フォードアルゴリズムは、エッジの重みが負の値をとる可能性がある場合でも、単一始点問題を解決します。
• A*探索アルゴリズムは、ヒューリスティックを用いて探索速度を向上させることで、単一ペアの最短経路を解きます。
• フロイド・ウォーシャルアルゴリズムは、すべてのペア間の最短経路を解きます。
• ジョンソンのアルゴリズムはすべてのペアの最短経路を解き、疎グラフではフロイド・ウォーシャルよりも高速である可能性がある。
• ビタビアルゴリズムは、各ノードに追加の確率的重みを付けることで、最短確率経路問題を解決する。

追加のアルゴリズムと関連する評価については、Cherkassky、Goldberg 、 Radzik (1996)を参照してください。

ネットワークフロー^{[ 12 ]}は、グラフ理論とオペレーションズリサーチにおける基本的な概念であり、ネットワークを介した商品、液体、または情報の輸送に関する問題をモデル化するためによく使用されます。ネットワークフロー問題では、通常、各エッジがパイプ、ワイヤー、または道路を表し、各エッジに容量（そこを流れることができる最大量）がある有向グラフが用いられます。目標は、ソースノードからシンクノードへのフローを最大化する実行可能なフローを見つけることです。

最短経路問題は、特に単一ソース・単一シンクのネットワークを扱う場合など、特定のネットワークフロー問題を解決するために利用できます。このようなシナリオでは、ネットワークフロー問題を一連の最短経路問題に変換することができます。

全ペア最短経路問題は、グラフ内のすべての頂点ペアv、v' 間の最短経路を見つけます。重みなし有向グラフの全ペア最短経路問題はShimbel (1953)によって導入され、彼は、この問題がO ( V ⁴ )の合計時間で線形数の行列乗算によって解決できることを観察しました。

最短経路アルゴリズムは、 MapQuestやGoogle MapsなどのWebマッピングWebサイトでの運転ルートなど、物理的な場所間の経路を自動的に見つけるために適用されます。このアプリケーションには、高速で専用のアルゴリズムが利用可能です。^{[ 16 ]}

非決定性抽象機械を、頂点が状態を表し、辺が可能な遷移を表すグラフとして表現する場合、最短経路アルゴリズムを用いて、特定の目標状態に到達するための最適な選択シーケンスを見つけたり、特定の状態に到達するのに必要な時間の下限を算出したりすることができます。例えば、頂点がルービックキューブのようなパズルの状態を表し、各有向辺が1回の移動または回転に対応する場合、最短経路アルゴリズムを用いて、最小限の移動回数で解を見つけることができます。

ネットワークや電気通信の観点から見ると、この最短経路問題は最小遅延経路問題と呼ばれることもあり、通常は最大経路問題と関連付けられています。たとえば、アルゴリズムは最短（最小遅延）最大経路、または最大最短（最小遅延）経路を求める場合があります。^{[ 17 ]}

もっと気楽な応用例としては、「六次の隔たり」ゲームがあり、これは同じ映画に出演している映画スターなどのグラフから最短経路を見つけようとするものです。

その他の応用例としては、オペレーションズリサーチでよく研究されるプラントおよび施設のレイアウト、ロボット工学、輸送、VLSI設計などがある。^{[ 18 ]}

計算幾何学における最短経路問題については、ユークリッド最短経路を参照してください。

最短多重切断パス^{[ 21 ]}は、レプテーション理論の枠組みにおける原始パスネットワークの表現である。最大パス問題は、任意のエッジの最小ラベルが可能な限り大きくなるようなパスを求める。

その他の関連問題は、以下のカテゴリーに分類できる。

多くの問題は、経路に沿った加算と最小値を取るという適切な置換概念を用いた最短経路問題として定式化できます。これらの一般的なアプローチは、2 つの演算を半環の演算とみなすことです。半環の乗算は経路に沿って行われ、加算は経路間で行われます。この一般的な枠組みは、代数経路問題として知られています。^{[ 27 ] [ 28 ] [ 29 ]}

古典的な最短経路アルゴリズム（および新しいアルゴリズム）のほとんどは、このような代数構造上の線形システムを解く問題として定式化できる。^{[ 30 ]}

さらに最近では、これらの問題（およびそれほど明白に関連しない問題）を解決するための、より一般的な枠組みが評価代数という名の下に開発されました。^{[ 31 ]}

現実世界では、交通ネットワークは通常、確率的で時間依存的です。道路区間の移動時間は、交通量（出発地-目的地マトリックス）、道路工事、天候、事故、車両故障など、多くの要因に依存します。このような道路ネットワークのより現実的なモデルは、確率的時間依存（STD）ネットワークです。^{[ 32 ] [ 33 ]}

不確実性下（すなわち、確率的な道路ネットワーク）における最適経路の定義は確立されていません。過去10年間でかなりの進歩があったにもかかわらず、これは依然として議論の的となっています。一般的な定義の一つは、期待移動時間が最小となる経路です。このアプローチの主な利点は、決定論的なネットワークに対して効率的な最短経路アルゴリズムを利用できることです。しかし、このアプローチでは移動時間の変動性を考慮していないため、得られる最適経路は必ずしも信頼できるとは限りません。

この問題に対処するため、一部の研究者は期待値の代わりに移動時間の分布を使用します。そのため、動的計画法やダイクストラ法などのさまざまな最適化手法を使用して、総移動時間の確率分布を見つけます。^{[ 34 ]}これらの手法は、確率的最適化、特に確率的動的計画法を使用して、確率的弧長を持つネットワークで最短経路を見つけます。^{[ 35 ]}移動時間の信頼性と移動時間の変動性という用語は、交通研究文献では反対の意味で使用されます。変動性が高いほど、予測の信頼性は低くなります。

変動性を考慮するため、研究者たちは不確実性下における最適経路の2つの代替定義を提案している。最も信頼性の高い経路とは、与えられた移動時間予算内で時間通りに到着する確率を最大化する経路である。α信頼性経路とは、与えられた確率で時間通りに到着するために必要な移動時間予算を最小化する経路である。

制限付き最短経路問題 (RSP)は、 2 つの最適化基準がある最短経路問題の変種です。各辺eに非負整数のコストc _eと非負整数の遅延 d _eを持つ有向グラフ、2 つの指定頂点 s と t、および非負整数の遅延予算Bが与えられます。目標は、総遅延が最大Bである経路の中から、総コストが最小のs-t経路を見つけることです。RSP は NP 困難です。Garey と Johnson の著書では、問題 ND30「最短重み制約付き経路」として登場します。Hassin ^{[ 36 ]}によるFPTASがあり、後に Lorenz と Raz ^{[ 37 ]によって簡略化および改良されました。}

この問題にはいくつかの一般化が知られている。

• リソース制約付き最短経路 (RCSP) ^{[ 38 ]}では、各エッジは (時間だけでなく) 複数のリソースを消費することができます。各リソースrには独立した予算B _rがあります。各エッジe は、各リソースrのd _e,rを消費します。目標は、各リソースのリソース制約を満たす経路の中から、総コストが最小となる s--t 経路を見つけることです。
• 共有マルチCSP問題^{[ 39 ]}では、 j=1,2,...に対して複数のソース-ターゲットペア( s _j , t _j )が存在する可能性があります。ここでは、各ソース-ターゲットペアに対して、総遅延が遅延予算以下であるという制約の下で、総コストが最小となるパスを見つけることが目標です。
• 分数RSPはRSPの線形計画緩和です。HandlerとZang ^{[ 40 ]}はこれを導入し、(リソースが1つの場合)それを解くための組み合わせアルゴリズムを示しました。MehlhornとZiegelmann ^{[ 38 ]}は、リソースが1つの場合、組み合わせアルゴリズムは多項式時間O(log( nCD ))で実行されることを証明しました。ここで、nはノードの数、コストは0..Cの整数、遅延は0..Dの整数です。リソースが多数の場合、組み合わせアルゴリズムの実行時間は未解決のままですが、楕円体法を使用するとLPを弱多項式時間で解くことができます。

• 双方向探索– 有向グラフ上の2つの頂点間の最短経路を見つけるアルゴリズム
• ユークリッド最短経路問題 – 幾何学的障害物を迂回する最短経路を計算する問題 
• フローネットワーク– エッジに容量を持つ有向グラフ 
• K最短経路ルーティング– グラフ理論の計算問題 
• 最小値プラス行列乗算– 行列に対する数学演算 
• 経路探索– コンピュータアプリケーションによるプロット 
• 最短経路ブリッジング
• 最短経路ツリー– スパニングツリーの一種リダイレクト先の簡単な説明を表示するページ 
• TRILL（多数のリンクの透明な相互接続）

• Altıntaş, Gökhan (2020).機械的類推に基づく最短経路問題の厳密解：迷路との関連において. Amazon Digital Services LLC. ISBN 9798655831896。
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "完全動的出力制限単一ソース最短経路問題".第 7 回 ACM-SIAM 離散アルゴリズムシンポジウム議事録. アトランタ、ジョージア州. pp. 212–221 . CiteSeerX 10.1.1.32.9856 .  
• Dreyfus, SE (1967年10月).最短経路アルゴリズムの評価(PDF) (報告書). プロジェクト・ランド. アメリカ空軍. RM-5433-PR. 2015年11月17日にオリジナルからアーカイブ(PDF) 。DTIC AD-661265。