最短経路問題

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

道路地図上の 2 つの交差点間の最短経路を見つける問題は、グラフの最短経路問題の特殊なケースとしてモデル化できます。この場合、頂点は交差点に対応し、エッジは道路セグメントに対応し、各セグメントの長さまたは距離によって重み付けされます。

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

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}}$

と の両方に接続する辺をとします。実数値の重み関数と無向（単純）グラフが与えられた場合、からへの最短経路は、および の経路全体で の合計を最小化する経路（ただしおよび）です。グラフの各辺に単位重み または がある場合、これは辺が最も少ない経路を見つけることと同等です。 ${\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\}}$

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

• 単一ソース最短経路問題。ソース頂点vからグラフ内の他のすべての頂点までの最短経路を見つける必要があります。
• 単一目的地最短経路問題。有向グラフ内のすべての頂点から単一の目的地頂点vまでの最短経路を見つける必要があります。これは、有向グラフの弧を逆にすることで、単一ソース最短経路問題に簡略化できます。
• 全ペア最短経路問題。グラフ内の頂点v、v'のすべてのペア間の最短経路を見つける必要があります。

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

この問題とその変種を解決するためのよく知られたアルゴリズムがいくつかあります。

• ダイクストラのアルゴリズムは、非負のエッジ重みのみを使用して、単一ソースの最短経路問題を解決します。
• ベルマン・フォード アルゴリズムは、エッジの重みが負になる可能性がある場合に、単一ソースの問題を解決します。
• A* 検索アルゴリズムは、ヒューリスティックを使用して単一ペアの最短経路を解き、検索を高速化します。
• フロイド・ワーシャルアルゴリズムはすべてのペアの最短経路を解きます。
• ジョンソンのアルゴリズムはすべてのペアの最短経路を解き、疎なグラフではフロイド・ワーシャルのアルゴリズムよりも高速になる可能性があります。
• Viterbi アルゴリズムは、各ノードに追加の確率的重みを付けて、最短確率経路問題を解決します。

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

トポロジカルソートを用いたアルゴリズムは、任意の重みを持つ有向非巡回グラフにおける単一ソース最短経路問題をΘ( E + V )の時間で解くことができる。 ^[3]

次の表は、Schrijver (2004) から引用したもので、いくつかの修正と追加が加えられています。緑の背景は、表の中で漸近的に最良の境界を示しています。Lは、すべてのエッジの最大長さ (または重み) で、エッジの重みが整数であると仮定しています。

負のサイクルを見つけるか、すべての頂点までの距離を計算します。

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

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

^[7]

1. 残差グラフを作成する:
   • 元のグラフの各エッジ (u, v) に対して、残差グラフに 2 つのエッジを作成します。
     • (u, v) の容量は c(u, v) です。
     • (v, u) 容量 0
   • 残余グラフは、ネットワークで使用可能な残りの容量を表します。
2. 最短経路を見つける:
   • 最短経路アルゴリズム (ダイクストラ アルゴリズム、ベルマン フォード アルゴリズムなど) を使用して、残差グラフ内のソース ノードからシンク ノードまでの最短経路を見つけます。
3. フローを増強する:
   • 最短経路に沿って最小容量を見つけます。
   • この最小容量によって、最短パスのエッジのフローが増加します。
   • 前方方向のエッジの容量を減らし、後方方向のエッジの容量を増やします。
4. 残差グラフを更新します。
   • 拡張フローに基づいて残差グラフを更新します。
5. 繰り返す：
   • ソースからシンクへのパスが見つからなくなるまで、手順 2 ～ 4 を繰り返します。

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

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

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

ネットワークや通信の観点では、この最短経路問題は、最小遅延経路問題と呼ばれることもあり、通常は最大幅経路問題と結び付けられます。たとえば、アルゴリズムは最短 (最小遅延) で最長の経路、または最も幅の広い最短 (最小遅延) の経路を探します。

もっと気楽な応用としては、同じ映画に登場する映画スターのようにグラフ内で最短経路を見つけようとする 「 6次の隔たり」ゲームがあります。

その他の応用分野としては、オペレーションズリサーチでよく研究されるものには、工場や施設のレイアウト、ロボット工学、輸送、VLSI設計などがある。^[11]

道路網は、正の重みを持つグラフとして考えることができます。ノードは道路の交差点を表し、グラフの各エッジは、2 つの交差点間の道路セグメントに関連付けられています。エッジの重みは、関連付けられた道路セグメントの長さ、セグメントを通過するのに必要な時間、またはセグメントを通過するコストに対応します。有向エッジを使用すると、一方通行の道路をモデル化することもできます。このようなグラフは、一部のエッジが長距離移動 (高速道路など) にとって他のエッジよりも重要であるという意味で特殊です。この特性は、高速道路の次元の概念を使用して形式化されています。^[12]この特性を利用するアルゴリズムは多数あり、そのため、一般的なグラフで可能であるよりもはるかに速く最短経路を計算できます。

これらのアルゴリズムはすべて 2 つのフェーズで動作します。最初のフェーズでは、ソース ノードまたはターゲット ノードがわからない状態でグラフが前処理されます。2 番目のフェーズはクエリ フェーズです。このフェーズでは、ソース ノードとターゲット ノードがわかっています。道路ネットワークは静的であるため、前処理フェーズを 1 回実行して、同じ道路ネットワークに対する多数のクエリに使用できます。

最も高速なクエリ時間を持つアルゴリズムはハブラベリングと呼ばれ、ヨーロッパや米国の道路網上の最短経路をマイクロ秒未満で計算することができます。^[13]他に使用されている技術は次のとおりです。

• ALT ( A* 検索、ランドマーク、三角不等式)
• アークフラグ
• 短縮階層
• トランジットノードルーティング
• リーチベースの剪定
• ラベリング
• ハブラベル

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

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

その他の関連する問題は、次のカテゴリに分類できます。

負の閉路のないグラフで多項式時間で解くことができる最短経路問題とは異なり、望ましい解の経路に追加の制約を含む最短経路問題は制約付き最短経路優先と呼ばれ、解くのがより困難です。 1 つの例は制約付き最短経路問題で、^[15]経路の総コストを最小化すると同時に別のメトリックを所定のしきい値以下に維持しようとします。 これにより、問題はNP 完全になります(このような問題は大規模なデータセットでは効率的に解くことができないと考えられています。 P = NP 問題を参照)。 別のNP 完全な例では、特定の頂点セットが経路に含まれる必要があり、^{[16]この問題が}巡回セールスマン問題(TSP)に似ています。 TSP は、すべての頂点を 1 回だけ通過して開始点に戻る最短経路を見つける問題です。グラフで 最長経路を見つける問題も NP 完全です。

カナダ人旅行者問題と確率的最短経路問題は、グラフが移動者に完全には知られていない、時間の経過とともに変化する、またはアクション（トラバーサル）が確率的である場合の一般化です。^{[17] [18]}

グラフのエッジには個性がある場合があります。つまり、各エッジには独自の利己的な関心があります。一例として、各エッジがおそらく異なる人物のコンピュータである通信ネットワークが挙げられます。コンピュータによって送信速度が異なるため、ネットワーク内のすべてのエッジには、メッセージを送信するのにかかるミリ秒数に等しい数値の重みがあります。私たちの目標は、ネットワーク内の 2 つのポイント間で可能な限り短い時間でメッセージを送信することです。各コンピュータの送信時間 (各エッジの重み) がわかっている場合は、標準的な最短経路アルゴリズムを使用できます。送信時間がわからない場合は、各コンピュータに送信時間を伝えるように依頼する必要があります。しかし、コンピュータは利己的である可能性があります。コンピュータは、送信時間が非常に長いことを私たちに伝え、私たちがメッセージで煩わせないようにする可能性があります。この問題の考えられる解決策は、コンピュータに実際の重みを明らかにするインセンティブを与える VCG メカニズムのバリエーションを使用することです。

場合によっては、主な目的は最短経路を見つけることではなく、グラフに負のサイクルがあるかどうかを検出することだけです。この目的には、いくつかの最短経路アルゴリズムを使用できます。

• ベルマン・フォードアルゴリズムは、時間内の負のサイクルを検出するために使用できます。${\displaystyle O(|V||E|)}$
• CherkasskyとGoldberg ^[19]は負のサイクル検出のための他のいくつかのアルゴリズムを調査した。

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

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

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

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

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

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

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

• 双方向探索、有向グラフ上の2つの頂点間の最短経路を見つけるアルゴリズム
• ユークリッド最短経路
• フローネットワーク
• K最短経路ルーティング
• 最小プラス行列乗算
• パスファインディング
• 最短経路ブリッジング
• 最短経路ツリー
• TRILL (多数のリンクの透過的な相互接続)

• アルトゥンタシュ、ゴカン（2020）。機械的な類推に基づく最短経路問題の正確な解：迷路との関連で。Amazon Digital Services LLC。ISBN 9798655831896。
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). 「完全に動的な出力制限付き単一ソース最短経路問題」。Proc . 7th Annu. ACM-SIAM Symp. 離散アルゴリズム。アトランタ、ジョージア州。pp. 212–221。CiteSeerX 10.1.1.32.9856 。
• Dreyfus, SE (1967 年 10 月)。「いくつかの最短経路アルゴリズムの評価(PDF) (レポート)」。プロジェクト Rand。米国空軍。RM-5433-PR。2015年 11 月 17 日のオリジナルからアーカイブ(PDF) 。DTIC AD-661265。