最短経路問題

重み付き有向グラフの頂点AとF間の最短経路（A、C、E、D、F）、青

グラフ理論において、最短経路問題とは、グラフを構成する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}}$

と の両方に接続する辺をとします。実数値の重み関数、および無向（単純）グラフが与えられている場合、 からへの最短経路は、すべての可能な経路にわたって の合計を最小化する経路（ただしおよび）です。グラフの各辺が単位重み または のとき、これは辺が最も少ない経路を見つけることに相当します。 ${\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) を参照してください。

単一始点最短経路

無向グラフ

重み	時間計算量	著者
${\displaystyle \mathbb {R} }$ ＋	O ( V ^2 )	ダイクストラ 1959
${\displaystyle \mathbb {R} }$ ＋	O (( E  +  V ) log  V )	ジョンソン 1977 (バイナリヒープ)
${\displaystyle \mathbb {R} }$ ＋	O ( E  +  V  log  V )	Fredman & Tarjan 1984 (フィボナッチ ヒープ)
${\displaystyle \mathbb {N} }$	O ( E )	Thorup 1999 (定数時間の乗算が必要)
${\displaystyle \mathbb {R} }$ ＋	${\displaystyle O(E{\sqrt {\log V\log \log V}})}$	ドゥアンら 2023

重みなしグラフ

アルゴリズム	時間計算量	著者
幅優先探索	O ( E  +  V )

有向非巡回グラフ

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

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

以下の表はSchrijver (2004) から引用したもので、いくつか修正と追加が加えられています。緑色の背景は、表の中で漸近的に最適な境界を示しています。Lは、すべての辺の中で最大の長さ（または重み）です（辺の重みが整数であると仮定した場合）。

重み	アルゴリズム	時間計算量	著者
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}EL)}$	フォード 1956
${\displaystyle \mathbb {R} }$	ベルマン・フォード法	${\displaystyle O(VE)}$	シンベル 1955、ベルマン 1958、ムーア 1959
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}\log{V})}$	Dantzig 1960
${\displaystyle \mathbb {R} }$	リストを用いたダイクストラのアルゴリズム	${\displaystyle O(V^{2})}$	Leyzorek et al. 1957、Dijkstra 1959、Minty（Pollack & Wiebenson 1960参照）、Whiting & Hillier 1960
${\displaystyle \mathbb {R} }$	二分ヒープを用いたダイクストラアルゴリズム	${\displaystyle O((E+V)\log{V})}$	ジョンソン 1977
${\displaystyle \mathbb {R} }$	フィボナッチヒープを用いたダイクストラ法	${\displaystyle O(E+V\log{V})}$	フレッドマンとタージャン 1984、フレッドマンとタージャン 1987
${\displaystyle \mathbb {R} }$	隣接リストを用いた量子ダイクストラアルゴリズム	${\displaystyle O({\sqrt {VE}}\log ^{2}{V})}$	デュールら 2006 [5]
${\displaystyle \mathbb {R} }$	ダイクストラ法とベルマン・フォード法のハイブリッドと分割統治法によるフロンティア縮小	${\displaystyle O(E\log^{2/3}{V})}$	ドゥアンら 2025 [6]
${\displaystyle \mathbb {N} }$	ダイアルのアルゴリズム[7]（L個のバケットを持つバケットキューを使用したダイクストラのアルゴリズム）	${\displaystyle O(E+LV)}$	ダイアル 1969
		${\displaystyle O(E\log {\log {L}})}$	ジョンソン 1981、カールソン＆ポブレテ 1983
	ガボウのアルゴリズム	${\displaystyle O(E\log_{E/V}L)}$	ガボウ 1983、ガボウ 1985
		${\displaystyle O(E+V{\sqrt{\log{L}}})}$	アフージャら 1990
${\displaystyle \mathbb {N} }$	ソールプ	${\displaystyle O(E+V\log{\log{V}})}$	ソールプ 2004

負の閉路を持たない任意の重みを持つ有向グラフ

重み	アルゴリズム	時間計算量	著者
${\displaystyle \mathbb {R} }$		${\displaystyle O(V^{2}EL)}$	フォード 1956
${\displaystyle \mathbb {R} }$	ベルマン・フォード法	${\displaystyle O(VE)}$	シンベル 1955、ベルマン 1958、ムーア 1959
${\displaystyle \mathbb {R} }$	二分ヒープを用いたジョンソン・ダイクストラ法	${\displaystyle O(VE+V\log V)}$	ジョンソン 1977
${\displaystyle \mathbb {R} }$	フィボナッチヒープを用いたジョンソン・ダイクストラ	${\displaystyle O(VE+V\log V)}$	フレッドマンとタージャン 1984、フレッドマンとタージャン 1987、ジョンソン 1977 の後に改作
${\displaystyle \mathbb {Z} }$	ジョンソンの手法をダイアルのアルゴリズムに適用した[7]	${\displaystyle O(V(E+L))}$	ダイヤル 1969、ジョンソン 1977 を基に改作
${\displaystyle \mathbb {Z} }$	ラプラシアンソルバーを用いた 内点法	${\displaystyle O(E^{10/7}\log^{O(1)}V\log^{O(1)}L)}$	コーエンら 2017
${\displaystyle \mathbb {Z} }$	フローソルバー を用いた内点法${\displaystyle \ell_{p}}$	${\displaystyle E^{4/3+o(1)}\log^{O(1)}L}$	アキシオティス、マドリ＆ヴラドゥ 2020
${\displaystyle \mathbb {Z} }$	スケッチによる ロバストな内点法	${\displaystyle O((E+V^{3/2})\log^{O(1)}V\log^{O(1)}L)}$	ファン・デン・ブランド他 2020
${\displaystyle \mathbb {Z} }$	${\displaystyle \ell_{1}}$ 動的最小比率サイクルデータ構造を持つ 内点法	${\displaystyle O(E^{1+o(1)}\log L)}$	チェンら 2022
${\displaystyle \mathbb {Z} }$	低直径分解に基づく	${\displaystyle O(E\log ^{8}V\log L)}$	バーンスタイン、ナノンカイ、ウルフ＝ニルセン 2022
${\displaystyle \mathbb {R} }$	ホップ制限付き最短経路	${\displaystyle O(EV^{8/9}\log^{O(1)}V)}$	ファインマン 2024

負の閉路を持つ任意の重みを持つ有向グラフ

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

重み	アルゴリズム	時間計算量	著者
${\displaystyle \mathbb {Z} }$		${\displaystyle O(E{\sqrt {V}}\log {N})}$	アンドリュー・V・ゴールドバーグ

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

重み	アルゴリズム	時間計算量	著者
${\displaystyle \mathbb {R} _{\geq 0}}$		${\displaystyle O(V)}$	ヘンジンガー他 1997

応用

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

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

変換手順

^[9]

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

全ペア最短経路

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

無向グラフ

重み	時間計算量	アルゴリズム
${\displaystyle \mathbb {R} }$ ＋	O ( V ^3 )	フロイド・ワーシャルアルゴリズム
${\displaystyle \{1,\infty \}}$	${\displaystyle O(V^{\omega }\log V)}$	ザイデルのアルゴリズム（高速行列乗算アルゴリズムを使用した場合の予想実行時間）
${\displaystyle \mathbb {N} }$	${\displaystyle O(V^{3}/2^{\Ω (\log V)^{1/2}})}$	ウィリアムズ 2014
${\displaystyle \mathbb {R} }$ ＋	O ( EV  log α( E , V ))	ペティ＆ラマチャンドラン 2002
${\displaystyle \mathbb {N} }$	O ( EV )	Thorup 1999 をすべての頂点に適用します (定数時間の乗算が必要です)。

有向グラフ

重み	時間計算量	アルゴリズム
${\displaystyle \mathbb {R} }$ （負の閉路なし）	${\displaystyle O(V^{3})}$	フロイド・ワーシャルアルゴリズム
${\displaystyle \mathbb {N} }$	${\displaystyle O(V^{3}/2^{\Ω (\log V)^{1/2}})}$	ウィリアムズ 2014
${\displaystyle \mathbb {R} }$ （負の閉路なし）	${\displaystyle O(V^{2.5}\log^{2}{V})}$	量子探索[10] [11]
${\displaystyle \mathbb {R} }$ （負の閉路なし）	O ( EV  +  V ^2  log  V )	ジョンソン・ダイクストラ
${\displaystyle \mathbb {R} }$ （負の閉路なし）	O ( EV  +  V ^2  log log  V )	ペティ 2004
${\displaystyle \mathbb {N} }$	O ( EV  +  V ^2  log log  V )	ヘーゲルップ 2000

応用

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

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

ネットワークや通信の分野では、この最短経路問題は最小遅延経路問題と呼ばれることもあり、通常は最大経路問題と結び付けられます。例えば、このアルゴリズムは最短（最小遅延）かつ最大幅の経路を求める場合もあれば、最短（最小遅延）かつ最大幅の経路を求める場合もあります。^[13]

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

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

道路網

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

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

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

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

関連問題

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

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

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

制約付き経路

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

部分的観測可能性

カナダ人旅行者問題と確率的最短経路問題は、グラフが移動者に完全には知られていない、時間の経過とともに変化する、または行動（通過）が確率的である場合の一般化です。^{[20] [21]}

戦略的最短経路

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

負の閉路検出

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

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

半環上の一般的な代数的枠組み：代数的経路問題

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

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

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

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

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

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

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

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

参照

• 双方向探索- 有向グラフ上の2つの頂点間の最短経路を見つけるアルゴリズム
• ユークリッド最短経路 – 幾何学的障害物を迂回する最短経路を計算する問題
• フローネットワーク – エッジに容量がある有向グラフ
• K最短経路ルーティング – グラフ理論の計算問題
• 最小プラス行列乗算 – 行列上の数学的演算
• 経路探索 – コンピュータアプリケーションによるプロット
• 最短経路ブリッジング
• 最短経路木 - スパニングツリーの一種Pages displaying short descriptions of redirect targets
• TRILL（多数のリンクの透過的な相互接続）

参考文献

注記

1. オルテガ＝アランツ、ヘクター、リャノス、ディエゴ・R.、ゴンザレス＝エスクリバノ、アルトゥーロ (2015). 最短経路問題. 理論計算機科学の統合講義. シュプリンガー出版. doi :10.1007/978-3-031-02574-7. ISBN 978-3-031-01446-8。
2. ゲニン、ベルトラン (2014).最適化入門. ヨッヘン・ケーネマン、レヴェント・トゥンチェル (第1版). ウェスト・ナイアック: ケンブリッジ大学出版局. 27ページ. ISBN 978-1-107-05344-1。
3. Deo, Narsingh (2016年8月17日). グラフ理論と工学およびコンピュータサイエンスへの応用. Courier Dover Publications. ISBN 978-0-486-80793-5。
4. コーメン他 2001, p. 655
5. 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.
6. Brubaker, Ben (2025年8月6日). 「新しい方法は、最適なルートを見つけるための最速の方法だ」. Quanta Magazine . 2025年8月11日閲覧。
7. Dial, Robert B. (1969). 「アルゴリズム360：位相順序付けによる最短経路フォレスト [H]」Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID  6754003.
8. コーメン、トーマス・H.（2009年7月31日）『アルゴリズム入門（第3版）』MITプレス、ISBN 9780262533058。
9. クラインバーグ、ジョン、タルドス、エヴァ (2005). アルゴリズム設計（第1版）. アディソン・ウェスリー. ISBN 978-0321295354。
10. Dürr, C.; Høyer, P. (1996-07-18). 「最小値を見つけるための量子アルゴリズム」arXiv : quant-ph/ 9607014
11. Nayebi, Aran; Williams, VV (2014-10-22). 「構造化インスタンスにおける最短経路問題のための量子アルゴリズム」arXiv : 1410.6220 [quant-ph].
12. Sanders, Peter (2009年3月23日). 「高速ルート計画」. Google Tech Talk . 2021年12月11日時点のオリジナルよりアーカイブ。
13. Hoceini, S.; A. Mellouk; Y. Amirat (2005). 「K最短経路Qルーティング：通信ネットワークにおける新たなQoSルーティングアルゴリズム」. Networking - ICN 2005, Lecture Notes in Computer Science, Vol. 3421. Vol. 3421. Springer, Berlin, Heidelberg. pp.  164– 172. doi :10.1007/978-3-540-31957-3_21. ISBN 978-3-540-25338-9。
14. チェン、ダニー・Z.（1996年12月）「幾何学的経路計画問題のためのアルゴリズムとソフトウェアの開発」 ACMコンピューティングサーベイ28 （ 4es）。記事18。doi : 10.1145/242224.242246。S2CID 11761485
15. Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F.「ハイウェイ次元、最短経路、そして証明可能な効率性を持つアルゴリズム」ACM-SIAM Symposium on Discrete Algorithms、782–793ページ、2010年。
16. Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf 「道路網における最短経路のためのハブベースラベリングアルゴリズム」。実験アルゴリズムに関するシンポジウム、230～241ページ、2011年。
17. Kroger, Martin (2005). 「2次元および3次元ポリマー系における絡み合い解析のための最短多重切断経路」. Computer Physics Communications . 168 (3): 209– 232. Bibcode :2005CoPhC.168..209K. doi :10.1016/j.cpc.2005.01.020.
18. ロザノ, レオナルド; メダリア, アンドレ L (2013). 「制約付き最短経路問題に対する正確な解法について」. Computers & Operations Research . 40 (1): 378– 384. doi :10.1016/j.cor.2012.07.008.
19. Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). 「グラフ畳み込みネットワークと最適化ツリー探索による制約付き経路計画問題の最適解」2019 IEEE/RSJ 国際知能ロボット・システム会議 (IROS) . pp.  3519– 3525. arXiv : 2108.01036 . doi :10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID  210706773.
20. , Baruch (1991). 「カナダ人旅行者問題」.第2回ACM-SIAM離散アルゴリズムシンポジウム議事録: 261–270 . CiteSeerX 10.1.1.1088.3015 
21. Nikolova, Evdokia; Karger, David R. 「不確実性下でのルート計画：カナダ人旅行者問題」（PDF） .第23回人工知能全国会議（AAAI）議事録. pp.  969– 974. 2022年10月9日時点のオリジナルよりアーカイブ（PDF）されています。
22. Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). 「負のサイクル検出アルゴリズム」 .数理計画. 85 (2): 277– 311. doi :10.1007/s101070050058. ISSN  1436-4646. S2CID  79739.
23. ペア、クロード (1967)。 「Sur des Algorithmes pour des problèmes de cheminement dans lesgraphes finis」[有限グラフにおける経路問題のアルゴリズムについて]。ローゼンティール、ピエール編（編）。Théorie desgraphes (journées internationales d'études) [グラフ理論 (国際シンポジウム)]。ローマ（イタリア）、1966 年 7 月。デュノー（パリ）。ゴードンとブリーチ（ニューヨーク）。 p. 271.OCLC 901424694  。
24. デルニアーム、ジャン・クロード;ペア、クロード (1971)。Problèmes de cheminement dans lesgraphes [グラフの経路問題]。デュノー（パリ）。
25. バラス, ジョン; テオドラコプロス, ジョージ (2010年4月4日). ネットワークにおけるパス問題. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3。
26. ゴンドラン、ミシェル；ミヌー、ミシェル (2008). 「第4章」.グラフ、ダイオイド、半環：新しいモデルとアルゴリズム. シュプリンガー・サイエンス＆ビジネス・メディア. ISBN 978-0-387-75450-5。
27. Pouly, Marc; Kohlas, Jürg (2011). 「第6章 経路問題のための評価代数」.ジェネリック推論：自動推論のための統一理論. John Wiley & Sons. ISBN 978-1-118-01086-0。
28. Loui, RP, 1983. 確率的または多次元重みを持つグラフにおける最適経路。Communications of the ACM, 26(9), pp.670-676
29. 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.
30. Olya, Mohammad Hessam (2014). 「指数分布とガンマ分布を組み合わせた弧長における最短経路の探索」. International Journal of Operational Research . 21 (1): 25– 37. doi :10.1504/IJOR.2014.064020.
31. Olya, Mohammad Hessam (2014). 「正規確率分布弧長を持つ一般最短経路問題へのダイクストラ法の適用」. International Journal of Operational Research . 21 (2): 143– 154. doi :10.1504/IJOR.2014.064541.

参考文献

• 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) .
• Axiotis, Kyriakos; Mądry, Aleksander; Vladu, Adrian (2020). 「単位容量グラフにおける最小コストフローの高速化のための循環制御」. Irani, Sandy (編).第61回IEEEコンピュータサイエンス基礎シンポジウム, FOCS 2020, ノースカロライナ州ダーラム, 米国, 2020年11月16日～19日. IEEE. pp.  93– 104. arXiv : 2003.04863 . doi :10.1109/FOCS46700.2020.00018.
• ベルマン、リチャード(1958). 「経路問題について」.応用数学季刊誌. 16 : 87–90 . doi : 10.1090/qam/102435 . MR  0102435.
• バーンスタイン、アーロン、ナノンカイ、ダヌポン、ウルフ＝ニルセン、クリスチャン (2022). 「負の重みを持つ単一ソース最短経路の近線形時間」. 2022 IEEE 第63回コンピュータサイエンス基礎シンポジウム (FOCS) . IEEE. pp.  600– 611. arXiv : 2203.03456 . doi :10.1109/focs54457.2022.00063. ISBN 978-1-6654-5519-0 S2CID  247958461
• ファン・デン・ブランド、ヤン；リー、イン・タット；ナンオンカイ、ダヌポン；ペン、リチャード；サラヌラック、サッチャポール；シドフォード、アーロン；ソン、チャオ；ワン、ディ (2020)。「中程度に密なグラフにおけるほぼ線形時間での二部マッチング」。イラニ、サンディ（編）第61回IEEEコンピュータサイエンス基礎年次シンポジウム、FOCS 2020、米国ノースカロライナ州ダーラム、2020年11月16～19日。IEEE。pp.  919– 930。arXiv : 2009.01802。doi : 10.1109/FOCS46700.2020.00090
• 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.
• Cohen, Michael B.; Mądry, Aleksander; Sankowski, Piotr; Vladu, Adrian (2017). 「負の重みを持つ最短経路と単位容量の最小コストフローの時間内」. Klein, Philip N. (編).第28回ACM–SIAM離散アルゴリズムシンポジウムSODA 2017議事録, バルセロナ, スペイン, Hotel Porta Fira, 1月16日～19日. Society for Industrial and Applied Mathematics. pp.  752– 771. doi : 10.1137/1.9781611974782.48 .${\displaystyle {\tilde {O}}(m^{10/7}\log W)}$
• Duan, Ran; Mao, Jiayi; Shu, Xinkai; Yin, Longhui (2023). 「無向実重みグラフにおける単一ソース最短経路のランダム化アルゴリズム」. 2023 IEEE 第64回コンピュータサイエンス基礎シンポジウム (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
• チェルカスキー, ボリス V.;ゴールドバーグ, アンドリュー V.;ラジク, トマシュ (1996). 「最短経路アルゴリズム：理論と実験的評価」.数理計画. Ser. A. 73 (2): 129– 174. doi :10.1016/0025-5610(95)00021-6. MR  1392160.
• コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001) [1990]. 「単一源最短経路と全対最短経路」.アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. pp.  580– 642. ISBN 0-262-03293-7。
• ダンツィグ、GB（1960年1月）「ネットワークを通る最短経路について」経営科学、6 (2): 187–190 . doi :10.1287/mnsc.6.2.187
• ダイクストラ、EW (1959)。 「グラフに関連した 2 つの問題についてのメモ」。数学数学。1 : 269–271。土井:10.1007/BF01386390。S2CID  123284777。
• Fineman, Jeremy T. (2024). 「負の実数重みを持つ時間的単一ソース最短経路」。Mohar, Bojan、Shinkar, Igor、O'Donnell, Ryan (編)。第56回ACMコンピューティング理論シンポジウム議事録、STOC 2024、バンクーバー、ブリティッシュコロンビア州、カナダ、2024年6月24～28日。Association for Computing Machinery。pp.  3～ 14。arXiv : 2311.02520。doi :10.1145/3618260.3649614。${\displaystyle {\tilde {O}}(mn^{8/9})}$
• フォード, LR (1956). ネットワークフロー理論（報告書）. サンタモニカ, カリフォルニア州: RAND Corporation. P-923.
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1984).フィボナッチ・ヒープとネットワーク最適化アルゴリズムの改良におけるその利用. 第25回コンピュータサイエンス基礎シンポジウム. IEEE . pp.  338– 346. doi :10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X。
• Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). 「フィボナッチ・ヒープと改良されたネットワーク最適化アルゴリズムにおけるその利用」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.
• ガボウ、ハロルド・N. (1985). 「ネットワーク問題のためのスケーリングアルゴリズム」.コンピュータとシステム科学ジャーナル. 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。
• ヘンジンガー、モニカ・R.；クライン、フィリップ；ラオ、サティッシュ；スブラマニアン、サイラム (1997).「平面グラフのための高速最短経路アルゴリズム」.コンピュータとシステム科学ジャーナル. 55 (1): 3–23 . doi : 10.1006/ jcss.1997.1493
• ジョンソン、ドナルド B. (1977). 「疎ネットワークにおける最短経路の効率的なアルゴリズム」. ACMジャーナル. 24 (1): 1– 13. doi : 10.1145/321992.321993 . S2CID  207678246.
• ジョンソン、ドナルド B. (1981年12月). 「初期化とキュー操作にO (log log D )時間を要する優先度付きキュー」.数理システム理論. 15 (1): 295– 309. doi :10.1007/BF01786986. MR  0683047. S2CID  35703411.
• Karlsson, Rolf G.; Poblete, Patricio V. (1983). 「最短経路を求めるO(m log log D)アルゴリズム」.離散応用数学. 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日 ― 通信システムのためのモデル技術の研究』オハイオ州クリーブランド：ケース工科大学.
• ムーア, EF (1959). 「迷路を通る最短経路」.スイッチング理論に関する国際シンポジウム議事録 (マサチューセッツ州ケンブリッジ、1957年4月2日～5日) . ケンブリッジ: ハーバード大学出版局. pp.  285– 292.
• ペティ, セス; ラマチャンドラン, ヴィジャヤ (2002). 「比較と加算による最短経路の計算」.第13回ACM-SIAM離散アルゴリズムシンポジウム議事録. pp. 267–276. ISBN 978-0-89871-513-2。
• ペティ、セス（2004年1月26日）「実重み付きグラフ上の全ペア最短経路への新しいアプローチ」理論計算機科学、312 (1): 47–74 . doi : 10.1016/s0304-3975(03)00402- x
• ポラック、モーリス；ウィーベンソン、ウォルター（1960年3～4月）「最短経路問題の解法――レビュー」Oper. Res . 8 (2): 224– 230. doi :10.1287/opre.8.2.224. 225 ページで、ダイクストラのアルゴリズムは Minty (「プライベート通信」) によるものだと説明しています。
• シュライバー、アレクサンダー (2004).組合せ最適化 — 多面体と効率性. アルゴリズムと組合せ論. 第24巻. シュプリンガー. A巻, セクション7.5b, p. 103. ISBN 978-3-540-20456-5。
• シンベル、アルフォンソ (1953). 「コミュニケーションネットワークの構造パラメータ」.数理生物物理学紀要. 15 (4): 501– 507. doi :10.1007/BF02476438.
• シンベル, 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.
• ウィリアムズ、ライアン(2014). 「回路計算量による全ペア最短経路の高速化」.第46回ACM計算理論シンポジウム(STOC '14)論文集. ニューヨーク: ACM. pp.  664– 673. arXiv : 1312.6680 . doi :10.1145/2591796.2591811. MR  3238994.

さらに読む

• アルトゥンタシュ、ギョカン（2020年）。『機械的アナロジーに基づく最短経路問題の厳密解：迷路との関連において』Amazon Digital Services LLC. ISBN 9798655831896。
• Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). 「完全動的出力有界単一ソース最短経路問題」. Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms . Atlanta, GA . pp.  212– 221. CiteSeerX  10.1.1.32.9856
• Dreyfus, SE (1967年10月). いくつかの最短経路アルゴリズムの評価(PDF) (報告書). プロジェクト・ランド. アメリカ空軍. RM-5433-PR. 2015年11月17日時点のオリジナルよりアーカイブ(PDF) .DTIC AD-661265