最短経路問題

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

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

意味

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

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

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

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

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

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

アルゴリズム

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

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

単一始点最短経路

無向グラフ

重み付けされていないグラフ

有向非巡回グラフ

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

非負の重みを持つ有向グラフ

以下の表は、 Schrijver (2004)から引用し、一部修正と加筆を加えたものです。緑色の背景は、表中の漸近的に最良の境界を示しています。Lは、すべてのエッジの中で最大の長さ（または重み）であり、エッジの重みは整数であると仮定しています。

負のサイクルを持たない、任意の重みを持つ有向グラフ

負のサイクルを持つ任意の重みを持つ有向グラフ

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

非負の重みを持つ平面グラフ

アプリケーション

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

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

変革のステップ

^{[ 13 ]}

残差グラフを作成する：
- 元のグラフの各エッジ(u, v)に対して、残余グラフに2つのエッジを作成します。
  - 容量 c(u, v) を持つ (u, v)
  - 容量0の(v, u)
- 残差グラフは、ネットワークに残っている利用可能な容量を表しています。
最短経路を見つける：
- 最短経路アルゴリズム（例：ダイクストラ法、ベルマン・フォード法）を使用して、残余グラフにおける始点ノードから終点ノードまでの最短経路を求めます。
流れを増強する：
- 最短経路に沿った最小容量を求めなさい。
- 最短経路の両端における流量を、この最小容量分だけ増加させる。
- 前方方向のエッジの容量を減らし、後方方向のエッジの容量を増やす。
残差グラフを更新する：
- 拡張されたフローに基づいて残差グラフを更新する。
繰り返す：
- 手順2～4を、ソースからシンクへの経路がなくなるまで繰り返します。

全ペア最短経路

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

無向グラフ

有向グラフ

アプリケーション

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

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

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

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

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

道路網

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

All of these algorithms work in two phases. In the first phase, the graph is preprocessed without knowing the source or target node. The second phase is the query phase. In this phase, source and target node are known. The idea is that the road network is static, so the preprocessing phase can be done once and used for a large number of queries on the same road network.

The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the US in a fraction of a microsecond.^[20] Other techniques that have been used are:

ALT (A* search, landmarks, and triangle inequality)
Arc flags
Contraction hierarchies
Transit node routing
Reach-based pruning
Labeling
Hub labels

半環に関する一般的な代数的枠組み：代数的経路問題

多くの問題は、経路に沿った加算と最小値を取るという適切な置換概念を用いた最短経路問題として定式化できます。これらの一般的なアプローチは、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 ^[³⁶^]によるFPTASがあり、後に Lorenz と Raz ^[³⁷^{]によって簡略化および改良されました。}

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

リソース制約付き最短経路 (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を弱多項式時間で解くことができます。

参考文献

注記

↑オルテガ＝アランツ、ヘクター。リャノス、ディエゴ R.ゴンザレス・エスクリバーノ、アルトゥーロ (2015)。最短経路問題。理論的なコンピュータサイエンスに関する総合講義。チャム：スプリンガー。土井: 10.1007/978-3-031-02574-7。ISBN 978-3-031-01446-8。
↑ Guenin, Bertrand (2014). Gentle Introduction to Optimization . Jochen Koenemann, Levent Tunçel (第1版). West Nyack: Cambridge University Press. p. 27. ISBN 978-1-107-05344-1。
↑デオ、ナルシング（2016年8月17日）。グラフ理論とその工学およびコンピュータ科学への応用。クーリエ・ドーバー出版。ISBN 978-0-486-80793-5。
↑ 「散歩道、小道、小道、自転車道、周回コース」。学生の学業成功。2026年7月13日取得。
↑ 「最短経路アルゴリズムのチュートリアルと問題」 . GeeksforGeeks . 2023-11-02 . 2026-07-13に閲覧。
↑ Brubaker, Ben (2025-08-06). 「新しい方法は最適なルートを見つける最速の方法」 . Quanta Magazine . 2026-07-13に閲覧。
↑コーメンら。 2001 年、p. 655
↑ Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi (2006 年 1 月)「いくつかのグラフ問題の量子クエリ複雑性」SIAM Journal on Computing . 35 (6): 1310–1328 . arXiv : quant-ph/0401091 . doi : 10.1137/050644719 . ISSN 0097-5397 . S2CID 14253494 .
↑ Brubaker, Ben (2025-08-06). 「新しい方法は最適なルートを見つける最速の方法」 . Quanta Magazine . 2025-08-11に取得.
1 2 Dial, Robert B. (1969). "アルゴリズム 360: トポロジカル順序付けによる最短経路フォレスト[ H ] " . Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID 6754003 .
↑ Khanna, Sanjeev; Song, Junkai (2026年2月18日). "単一始点負重み最短経路のためのn ²⁺^o^{(1)時間アルゴリズム".}arXiv : 2602.16638 [ cs.DS ].
↑コーメン、トーマス・H. （ 2009年7月31日）。アルゴリズム入門（第3版）。MIT Press。ISBN 9780262533058。
↑ジョン・クラインバーグ;タルドス、エヴァ (2005)。アルゴリズム設計(第 1版)。アディソン・ウェスリー。ISBN 978-0321295354。
↑ Dürr, C.; Høyer, P. (1996-07-18). "最小値を見つけるための量子アルゴリズム". arXiv : quant-ph/9607014 .
↑ Nayebi, Aran; Williams, VV (2014-10-22). "構造化インスタンスにおける最短経路問題のための量子アルゴリズム". arXiv : 1410.6220 [ quant-ph ].
↑サンダーズ、ピーター（2009年3月23日）。「高速ルートプランニング」。Google Tech Talk。2021年12月11日にオリジナルからアーカイブ済み。
↑ Hoceini, S.; A. Mellouk; Y. Amirat (2005). "K最短経路Qルーティング：電気通信ネットワークにおける新しいQoSルーティングアルゴリズム" . Networking - ICN 2005、Lecture Notes in Computer Science、Vol. 3421 . Vol. 3421. Springer、ベルリン、ハイデルベルク。pp. 164–172 . doi : 10.1007/978-3-540-31957-3_21 . ISBN 978-3-540-25338-9。
↑ Chen, Danny Z. (1996 年 12 月). 「幾何学的経路計画問題のためのアルゴリズムとソフトウェアの開発」. ACM Computing Surveys . 28 (4es). 論文 18. doi : 10.1145/242224.242246 . S2CID 11761485 .
↑ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V. ; Werneck, Renato F. "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms" . ACM-SIAM Symposium on Discrete Algorithms、782–793 ページ、2010 年。
↑ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V. ; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf 「道路ネットワーク上の最短経路のためのハブベースのラベリングアルゴリズム」実験アルゴリズムに関するシンポジウム、230～241ページ、2011年。
↑ Kroger, Martin (2005). "二次元および三次元高分子系における絡み合い解析のための最短多重非連結経路". Computer Physics Communications . 168 (3): 209–232 . Bibcode : 2005CoPhC.168..209K . doi : 10.1016/j.cpc.2005.01.020 .
↑ Lozano, Leonardo; Medaglia, Andrés L (2013). "制約付き最短経路問題に対する厳密解法について". Computers & Operations Research . 40 (1): 378– 384. doi : 10.1016/j.cor.2012.07.008 .
↑ Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "グラフ畳み込みネットワークと最適化されたツリー探索による制約付き経路計画問題の最適解法". 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . pp. 3519–3525 . arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113 . ISBN 978-1-7281-4004-9. S2CID 210706773 .
↑ Bar-Noy, Amotz; Schieber, Baruch (1991). "The canadian traveller problem". Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms : 261– 270. CiteSeerX 10.1.1.1088.3015 .
↑ Nikolova, Evdokia; Karger, David R. 「不確実性下での経路計画：カナダの旅行者問題」（PDF）。第23回人工知能全国会議（AAAI）議事録。pp. 969–974。2022年10月9日にオリジナルからアーカイブ（PDF）。
↑ Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "負のサイクル検出アルゴリズム" . Mathematical Programming . 85 (2): 277– 311. doi : 10.1007/s101070050058 . ISSN 1436-4646 . S2CID 79739 .
↑ペア、クロード (1967)。「Sur des Algorithms pour des problèmes de cheminement dans lesgraphes finis 」 [有限グラフにおける経路問題のアルゴリズムについて]。ローゼンティール、ピエール編（編）。Théorie desgraphes (journées internationales d'études) [グラフ理論 (国際シンポジウム)]。ローマ（イタリア）、1966 年 7 月。デュノー（パリ）。ゴードンとブリーチ（ニューヨーク）。 p. 271.OCLC 901424694。
↑デルニアム、ジャン・クロード。ペア、クロード (1971)。Problèmes de cheminement dans lesgraphes [グラフの経路問題]。デュノー（パリ）。
↑ Baras, John; Theodorakopoulos, George (2010年4月4日). Path Problems in Networks . Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3。
↑ゴンドラン、ミシェル；ミヌー、ミシェル（2008）。「第4章」。グラフ、ディオイド、半環：新しいモデルとアルゴリズム。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-0-387-75450-5。
↑ Pouly, Marc; Kohlas, Jürg (2011). 「第6章パス問題の評価代数」『汎用推論：自動推論のための統一理論』John Wiley & Sons. ISBN 978-1-118-01086-0。
↑ Loui, RP, 1983. 確率的または多次元重みを持つグラフにおける最適経路. Communications of the ACM, 26(9), pp.670-676.
↑ Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "非劣解ソート遺伝的アルゴリズムを用いた確率的時間依存道路ネットワークにおける多目的経路探索". Expert Systems with Applications . 42 (12): 5056– 5064. doi : 10.1016/j.eswa.2015.02.046 .
↑ Olya, Mohammad Hessam (2014). "Finding shortest path in a combined exponential – gamma probability distribution arc length". International Journal of Operational Research . 21 (1) 64020: 25– 37. doi : 10.1504/IJOR.2014.064020 .
↑ Olya, Mohammad Hessam (2014). "正規確率分布弧長を持つ一般最短経路問題へのダイクストラ法の適用". International Journal of Operational Research . 21 (2) 64541: 143– 154. doi : 10.1504/IJOR.2014.064541 .
↑ Hassin, Refael (1992 年 2 月) 「制限付き最短経路問題の近似スキーム」 . Mathematics of Operations Research . 17 (1): 36–42 . doi : 10.1287/moor.17.1.36 . ISSN 0364-765X .
↑ Lorenz, Dean H.; Raz, Danny (2001 年 6 月). "制限付き最短経路問題に対するシンプルで効率的な近似スキーム" . Operations Research Letters . 28 (5): 213– 219. doi : 10.1016/s0167-6377(01)00069-4 . ISSN 0167-6377 .
1 2 Mehlhorn, Kurt; Ziegelmann, Mark (2000). "Resource Constrained Shortest Paths" . In Paterson, Mike S. (ed.). Algorithms - ESA 2000 . Lecture Notes in Computer Science. Vol. 1879. Berlin, Heidelberg: Springer. pp. 326–337 . doi : 10.1007/3-540-45253-2_30 . ISBN 978-3-540-45253-9。
↑ García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio (2021年11月). "共有リソース制約付きマルチ最短経路問題の解法" . Expert Systems with Applications . 182 115193. doi : 10.1016/j.eswa.2021.115193 . hdl : 10016/30793 . ISSN 0957-4174 .
↑ Handler, Gabriel Y.; Zang, Israel (1980 年 12 月). "制約付き最短経路問題に対する双対アルゴリズム" . Networks . 10 (4): 293– 309. doi : 10.1002/net.3230100403 . ISSN 0028-3045 .

参考文献

Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (1990 年 4 月). 「最短経路問題のためのより高速なアルゴリズム」(PDF) . Journal of the ACM . 37 (2). ACM: 213–223 . doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589 . 2022 年 10 月 9 日にオリジナルからアーカイブ(PDF) 。
アクシオティス、キリアコス。マンドリー、アレクサンダー。ヴラドゥ、エイドリアン（2020）。「単位容量グラフの最小コストフローを高速化するための循環制御」。イラニにて、サンディ（編集）。第 61 回コンピュータサイエンスの基礎に関する IEEE 年次シンポジウム、FOCS 2020、米国ノースカロライナ州ダーラム、2020 年 11 月 16 ～ 19 日。 IEEE。ページ93–104。arXiv : 2003.04863。土井: 10.1109/FOCS46700.2020.00018。ISBN 978-1-7281-9621-3。
ベルマン、リチャード（1958）。「ルーティング問題について」。応用数学季刊誌。16 ：87–90。doi ：10.1090 / qam / 102435。MR 0102435 。
Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 600–611 . arXiv : 2203.03456 . doi : 10.1109/focs54457.2022.00063 . ISBN 978-1-6654-5519-0. S2CID 247958461 .
van den Brand, Jan; Lee, Yin Tat; Nanongkai, Danupon; Peng, Richard; Saranurak, Thatchaphol; Sidford, Aaron; Song, Zhao; Wang, Di (2020). "中密度グラフにおけるほぼ線形時間での二部グラフマッチング". Irani, Sandy (編).第61回IEEEコンピュータサイエンス基礎年次シンポジウム、FOCS 2020、米国ノースカロライナ州ダーラム、2020年11月16～19日. IEEE. pp. 919–930 . arXiv : 2009.01802 . doi : 10.1109/FOCS46700.2020.00090 . ISBN 978-1-7281-9621-3。
Chen, Li; Kyng, Rasmus; Liu, Yang P.; Peng, Richard; Gutenberg, Maximilian Probst; Sachdeva, Sushant (2022). "ほぼ線形時間での最大フローと最小コストフロー".第63回IEEEコンピュータサイエンス基礎年次シンポジウム、 FOCS 2022、米国コロラド州デンバー、2022年10月31日～11月3 日。IEEE。pp . 612–623。arXiv : 2203.00671。doi : 10.1109 / FOCS54457.2022.00064。ISBN 978-1-6654-5519-0。
Cohen, Michael B.; Mądry, Aleksander; Sankowski, Piotr; Vladu, Adrian (2017). 「負の重み最短経路と単位容量最小コストフロー ${\チルダ {O}}(m^{10/7}\log W)$ 時間」。Klein, Philip N. (編)『第28回ACM–SIAM離散アルゴリズムシンポジウム、SODA 2017議事録、スペイン、バルセロナ、ホテル・ポルタ・フィラ、1月16～19日』。応用数理学会。pp. 752–771。doi : 10.1137 / 1.9781611974782.48。
Duan, Ran; Mao, Jiayi; Shu, Xinkai; Yin, Longhui (2023). "無向実数重み付きグラフにおける単一始点最短経路のためのランダム化アルゴリズム". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 484–492 . arXiv : 2307.04139 . doi : 10.1109/focs57990.2023.00035 . ISBN 979-8-3503-1894-4. S2CID 259501045 .
Duan, Ran; Mao, Jiayi; Mao, Xiao; Shu, Xinkai; Yin, Longhui (2025). 「指向性単一始点最短経路におけるソート障壁の打破」.第57回ACM理論計算機科学シンポジウム（STOC）論文集. Association for Computing Machinery. pp. 36–44 . doi : 10.1145/3717823.3718179 . ISBN 979-8-4007-1510-5。
Cherkassky, Boris V.; Goldberg, Andrew V. ; Radzik, Tomasz (1996). "最短経路アルゴリズム: 理論と実験的評価" . Mathematical Programming . Ser. A. 73 (2): 129– 174. doi : 10.1016/0025-5610(95)00021-6 . MR 1392160 .
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. 「単一始点最短経路と全ペア最短経路」.アルゴリズム入門（第2 版）. MIT PressおよびMcGraw-Hill. pp. 580–642 . ISBN 0-262-03293-7。
Dantzig, GB (1960年1月)「ネットワークを通る最短経路について」Management Science . 6 (2): 187–190 . doi : 10.1287/mnsc.6.2.187 .
Dijkstra, EW (1959). "グラフに関連する2つの問題に関する注記". Numerische Mathematik . 1 : 269–271 . Bibcode : 1959NuMat...1..269D . doi : 10.1007/BF01386390 . S2CID 123284777 .
Fineman, Jeremy T. (2024). 「負の実数重みを持つ単一始点最短経路 ${\チルダ {O}}(mn^{8/9})$ 「時間」。Mohar, Bojan、Shinkar, Igor、O'Donnell, Ryan (編)『第56回ACM理論計算機科学シンポジウム、STOC 2024、バンクーバー、BC、カナダ、2024年6月24～28日』論文集。Association for Computing Machinery。pp . 3–14。arXiv : 2311.02520。doi : 10.1145/3618260.3649614。
フォード、LR（1956）。ネットワークフロー理論（報告書）。カリフォルニア州サンタモニカ：ランド研究所。P-923。
Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms . 25th Annual Symposium on Foundations of Computer Science. IEEE . pp. 338–346 . doi : 10.1109/SFCS.1984.715934 . ISBN 0-8186-0591-X。
Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms" . Journal of the Association for Computing Machinery . 34 (3): 596–615 . doi : 10.1145/28869.28874 . S2CID 7904683 .
Gabow, HN (1983). 「ネットワーク問題のためのスケーリングアルゴリズム」(PDF) .第24回コンピュータサイエンス基礎に関する年次シンポジウム(FOCS 1983) 論文集. pp. 248–258 . doi : 10.1109/SFCS.1983.68 .
Gabow, Harold N. (1985). 「ネットワーク問題のためのスケーリングアルゴリズム」 . Journal of Computer and System Sciences . 31 (2): 148– 168. doi : 10.1016/0022-0000(85)90039-X . MR 0828519 .
Hagerup, Torben (2000). 「ワードRAM上の最短経路の改善」 . Montanari, Ugo; Rolim, José DP; Welzl, Emo (編)『第27回オートマタ、言語、プログラミングに関する国際コロキウム議事録』 pp. 61–72 . ISBN 978-3-540-67715-4。
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). "平面グラフのためのより高速な最短経路アルゴリズム" . Journal of Computer and System Sciences . 55 (1): 3– 23. doi : 10.1006/jcss.1997.1493 .
Johnson, Donald B. (1977). "疎なネットワークにおける最短経路の効率的なアルゴリズム" . Journal of the ACM . 24 (1): 1– 12. doi : 10.1145/321992.321993 . S2CID 207678246 .
Johnson, Donald B. (1981年12月). 「初期化とキュー操作に $O (log log D)$ 時間を要する優先度付きキュー」. Mathematical Systems Theory . 15 (1): 295–309 . doi : 10.1007/BF01786986 . MR 0683047. S2CID 35703411 .
Karlsson, Rolf G.; Poblete, Patricio V. (1983). "最短経路のための $O (m log log D)$ アルゴリズム" . Discrete Applied Mathematics . 6 (1): 91– 93. doi : 10.1016/0166-218X(83)90104-X . MR 0700028 .
Leyzorek, M.; Gray, RS; Johnson, AA; Ladew, WC; Meaker, SR Jr.; Petry, RM; Seitz, RN (1957).モデル技術の調査 — 第 1 回年次報告 — 1956 年 6 月 6 日 — 1957 年 7 月 1 日 — 通信システムのためのモデル技術の研究。オハイオ州クリーブランド: Case Institute of Technology。
ムーア、EF（1959）。「迷路を通る最短経路」。スイッチング理論に関する国際シンポジウム議事録（マサチューセッツ州ケンブリッジ、1957年4月2日～5日）。ケンブリッジ：ハーバード大学出版局。pp. 285–292。
Pettie, Seth; Ramachandran, Vijaya (2002). 「比較と加算による最短経路の計算」 .第13回ACM-SIAM離散アルゴリズムシンポジウム議事録. pp. 267–276 . ISBN 978-0-89871-513-2。
Pettie, Seth (2004年1月26日). 「実数重み付きグラフにおける全ペア最短経路への新しいアプローチ」 . Theoretical Computer Science . 312 (1): 47–74 . doi : 10.1016/s0304-3975(03)00402-x .
ポラック、モーリス、ウィーベンソン、ウォルター（1960年3月～4月）。「最短経路問題の解法―レビュー」。オペレーションズリサーチ8 （ 2）：224～ 230。doi ：10.1287/opre.8.2.224。 225 ページで、ダイクストラのアルゴリズムはミンティによるものだと述べている（「私信」）。
Schrijver, Alexander (2004).組み合わせ最適化 ― 多面体と効率性. アルゴリズムと組み合わせ論. 第24巻. Springer. 第A巻、第7.5b節、 103 ページ. ISBN 978-3-540-20456-5。
Shimbel, Alfonso (1953). 「通信ネットワークの構造パラメータ」. Bulletin of Mathematical Biophysics . 15 (4): 501–507 . Bibcode : 1953BMaB...15..501S . doi : 10.1007/BF02476438 .
Shimbel, A. (1955). 「通信ネットワークの構造」.情報ネットワークに関するシンポジウム議事録. ニューヨーク州ニューヨーク: ブルックリン工科大学ポリテクニック出版. pp. 199–203 .
Thorup, Mikkel (1999). "線形時間で正の整数重みを持つ無向単一始点最短経路" . Journal of the ACM . 46 (3): 362–394 . doi : 10.1145/316542.316548 . S2CID 207654795 .
Thorup, Mikkel (2004). 「定数時間でキーが減少する整数優先度キューと単一ソース最短経路問題」 . Journal of Computer and System Sciences . 69 (3): 330–353 . doi : 10.1016/j.jcss.2004.04.003 .
Whiting, PD; Hillier, JA (1960年3月～6月)「道路網を通る最短経路を見つける方法」Operational Research Quarterly . 11 (1/2): 37–40 . doi : 10.1057/jors.1960.32 .
Williams, Ryan (2014). "回路複雑性による全ペア最短経路の高速化".第46回ACM理論計算機科学シンポジウム（STOC '14）論文集. ニューヨーク：ACM. pp. 664–673 . arXiv : 1312.6680 . doi : 10.1145/2591796.2591811 . MR 3238994 .

さらに読む

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。

[1] オルテガ＝アランツ、ヘクター。リャノス、ディエゴ R.ゴンザレス・エスクリバーノ、アルトゥーロ (2015)。最短経路問題。理論的なコンピュータサイエンスに関する総合講義。チャム：スプリンガー。土井: 10.1007/978-3-031-02574-7。ISBN 978-3-031-01446-8。

[2] Guenin, Bertrand (2014). Gentle Introduction to Optimization . Jochen Koenemann, Levent Tunçel (第1版). West Nyack: Cambridge University Press. p. 27. ISBN 978-1-107-05344-1。

[3] デオ、ナルシング（2016年8月17日）。グラフ理論とその工学およびコンピュータ科学への応用。クーリエ・ドーバー出版。ISBN 978-0-486-80793-5。

[4] 「散歩道、小道、小道、自転車道、周回コース」。学生の学業成功。2026年7月13日取得。

[5] 「最短経路アルゴリズムのチュートリアルと問題」 . GeeksforGeeks . 2023-11-02 . 2026-07-13に閲覧。

[6] Brubaker, Ben (2025-08-06). 「新しい方法は最適なルートを見つける最速の方法」 . Quanta Magazine . 2026-07-13に閲覧。

[7] コーメンら。 2001 年、p. 655

[8] Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi (2006 年 1 月)「いくつかのグラフ問題の量子クエリ複雑性」SIAM Journal on Computing . 35 (6): 1310–1328 . arXiv : quant-ph/0401091 . doi : 10.1137/050644719 . ISSN 0097-5397 . S2CID 14253494 .

[9] Brubaker, Ben (2025-08-06). 「新しい方法は最適なルートを見つける最速の方法」 . Quanta Magazine . 2025-08-11に取得.

[dial69-10] 1 2 Dial, Robert B. (1969). "アルゴリズム 360: トポロジカル順序付けによる最短経路フォレスト[ H ] " . Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID 6754003 .

[11] Khanna, Sanjeev; Song, Junkai (2026年2月18日). "単一始点負重み最短経路のためのn ²⁺^o^{(1)時間アルゴリズム".}arXiv : 2602.16638 [ cs.DS ].

[12] コーメン、トーマス・H. （ 2009年7月31日）。アルゴリズム入門（第3版）。MIT Press。ISBN 9780262533058。

[13] ジョン・クラインバーグ;タルドス、エヴァ (2005)。アルゴリズム設計(第 1版)。アディソン・ウェスリー。ISBN 978-0321295354。

[14] Dürr, C.; Høyer, P. (1996-07-18). "最小値を見つけるための量子アルゴリズム". arXiv : quant-ph/9607014 .

[15] Nayebi, Aran; Williams, VV (2014-10-22). "構造化インスタンスにおける最短経路問題のための量子アルゴリズム". arXiv : 1410.6220 [ quant-ph ].

[16] サンダーズ、ピーター（2009年3月23日）。「高速ルートプランニング」。Google Tech Talk。2021年12月11日にオリジナルからアーカイブ済み。

[17] Hoceini, S.; A. Mellouk; Y. Amirat (2005). "K最短経路Qルーティング：電気通信ネットワークにおける新しいQoSルーティングアルゴリズム" . Networking - ICN 2005、Lecture Notes in Computer Science、Vol. 3421 . Vol. 3421. Springer、ベルリン、ハイデルベルク。pp. 164–172 . doi : 10.1007/978-3-540-31957-3_21 . ISBN 978-3-540-25338-9。

[18] Chen, Danny Z. (1996 年 12 月). 「幾何学的経路計画問題のためのアルゴリズムとソフトウェアの開発」. ACM Computing Surveys . 28 (4es). 論文 18. doi : 10.1145/242224.242246 . S2CID 11761485 .

[19] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V. ; Werneck, Renato F. "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms" . ACM-SIAM Symposium on Discrete Algorithms、782–793 ページ、2010 年。

[20] Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V. ; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf 「道路ネットワーク上の最短経路のためのハブベースのラベリングアルゴリズム」実験アルゴリズムに関するシンポジウム、230～241ページ、2011年。

[21] Kroger, Martin (2005). "二次元および三次元高分子系における絡み合い解析のための最短多重非連結経路". Computer Physics Communications . 168 (3): 209–232 . Bibcode : 2005CoPhC.168..209K . doi : 10.1016/j.cpc.2005.01.020 .

[22] Lozano, Leonardo; Medaglia, Andrés L (2013). "制約付き最短経路問題に対する厳密解法について". Computers & Operations Research . 40 (1): 378– 384. doi : 10.1016/j.cor.2012.07.008 .

[23] Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "グラフ畳み込みネットワークと最適化されたツリー探索による制約付き経路計画問題の最適解法". 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . pp. 3519–3525 . arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113 . ISBN 978-1-7281-4004-9. S2CID 210706773 .

[24] Bar-Noy, Amotz; Schieber, Baruch (1991). "The canadian traveller problem". Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms : 261– 270. CiteSeerX 10.1.1.1088.3015 .

[25] Nikolova, Evdokia; Karger, David R. 「不確実性下での経路計画：カナダの旅行者問題」（PDF）。第23回人工知能全国会議（AAAI）議事録。pp. 969–974。2022年10月9日にオリジナルからアーカイブ（PDF）。

[26] Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "負のサイクル検出アルゴリズム" . Mathematical Programming . 85 (2): 277– 311. doi : 10.1007/s101070050058 . ISSN 1436-4646 . S2CID 79739 .

[Pair1966-27] ペア、クロード (1967)。「Sur des Algorithms pour des problèmes de cheminement dans lesgraphes finis 」 [有限グラフにおける経路問題のアルゴリズムについて]。ローゼンティール、ピエール編（編）。Théorie desgraphes (journées internationales d'études) [グラフ理論 (国際シンポジウム)]。ローマ（イタリア）、1966 年 7 月。デュノー（パリ）。ゴードンとブリーチ（ニューヨーク）。 p. 271.OCLC 901424694。

[28] デルニアム、ジャン・クロード。ペア、クロード (1971)。Problèmes de cheminement dans lesgraphes [グラフの経路問題]。デュノー（パリ）。

[BarasTheodorakopoulos2010-29] Baras, John; Theodorakopoulos, George (2010年4月4日). Path Problems in Networks . Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3。

[GondranMinoux2008-30] ゴンドラン、ミシェル；ミヌー、ミシェル（2008）。「第4章」。グラフ、ディオイド、半環：新しいモデルとアルゴリズム。シュプリンガー・サイエンス＆ビジネス・メディア。ISBN 978-0-387-75450-5。

[PoulyKohlas2012-31] Pouly, Marc; Kohlas, Jürg (2011). 「第6章パス問題の評価代数」『汎用推論：自動推論のための統一理論』John Wiley & Sons. ISBN 978-1-118-01086-0。

[32] Loui, RP, 1983. 確率的または多次元重みを持つグラフにおける最適経路. Communications of the ACM, 26(9), pp.670-676.

[33] Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "非劣解ソート遺伝的アルゴリズムを用いた確率的時間依存道路ネットワークにおける多目的経路探索". Expert Systems with Applications . 42 (12): 5056– 5064. doi : 10.1016/j.eswa.2015.02.046 .

[34] Olya, Mohammad Hessam (2014). "Finding shortest path in a combined exponential – gamma probability distribution arc length". International Journal of Operational Research . 21 (1) 64020: 25– 37. doi : 10.1504/IJOR.2014.064020 .

[35] Olya, Mohammad Hessam (2014). "正規確率分布弧長を持つ一般最短経路問題へのダイクストラ法の適用". International Journal of Operational Research . 21 (2) 64541: 143– 154. doi : 10.1504/IJOR.2014.064541 .

[36] Hassin, Refael (1992 年 2 月) 「制限付き最短経路問題の近似スキーム」 . Mathematics of Operations Research . 17 (1): 36–42 . doi : 10.1287/moor.17.1.36 . ISSN 0364-765X .

[37] Lorenz, Dean H.; Raz, Danny (2001 年 6 月). "制限付き最短経路問題に対するシンプルで効率的な近似スキーム" . Operations Research Letters . 28 (5): 213– 219. doi : 10.1016/s0167-6377(01)00069-4 . ISSN 0167-6377 .

[:0-38] 1 2 Mehlhorn, Kurt; Ziegelmann, Mark (2000). "Resource Constrained Shortest Paths" . In Paterson, Mike S. (ed.). Algorithms - ESA 2000 . Lecture Notes in Computer Science. Vol. 1879. Berlin, Heidelberg: Springer. pp. 326–337 . doi : 10.1007/3-540-45253-2_30 . ISBN 978-3-540-45253-9。

[39] García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio (2021年11月). "共有リソース制約付きマルチ最短経路問題の解法" . Expert Systems with Applications . 182 115193. doi : 10.1016/j.eswa.2021.115193 . hdl : 10016/30793 . ISSN 0957-4174 .

[40] Handler, Gabriel Y.; Zang, Israel (1980 年 12 月). "制約付き最短経路問題に対する双対アルゴリズム" . Networks . 10 (4): 293– 309. doi : 10.1002/net.3230100403 . ISSN 0028-3045 .

[

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 12 ]

[ 13 ]

[

[ 17 ]

[ 18 ]

[ 19 ]

[20]

[21]

[22]

[23]

[24]

[25]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[

[

[ 39 ]

[ 40 ]

最短経路問題

意味

アルゴリズム

単一始点最短経路

無向グラフ

重み付けされていないグラフ

有向非巡回グラフ

非負の重みを持つ有向グラフ

負のサイクルを持たない、任意の重みを持つ有向グラフ

負のサイクルを持つ任意の重みを持つ有向グラフ

非負の重みを持つ平面グラフ

アプリケーション

変革のステップ

全ペア最短経路

無向グラフ

有向グラフ

アプリケーション

道路網

Related problems

Paths with constraints

Partial observability

Strategic shortest paths

負のサイクル検出

半環に関する一般的な代数的枠組み：代数的経路問題

確率的時間依存ネットワークにおける最短経路

制限付き最短経路

関連項目

参考文献

注記

参考文献

さらに読む

関連するトピック

グラフ理論

グラフ内の2つの

頂点

経路を見つけ、その経路を構成する辺の