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

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

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

意味

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

2つの頂点が共通の辺に接している場合、それらの頂点は隣接していると言える。無向グラフにおけるパスとは、に対して がに隣接するような頂点の列である。このようなパスは、からまでの長さを持つパスと呼ばれる。（ は変数である。その番号は列内の位置に対応しており、標準的なラベル付けとは必ずしも関連していない。） P＝（v1、v2、…、vn）∈V×V×⋯×V{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}v私{\displaystyle v_{i}}v私+1{\displaystyle v_{i+1}}1≤私<n{\displaystyle 1\leq i<n}P{\displaystyle P}n−1{\displaystyle n-1}v1{\displaystyle v_{1}}vn{\displaystyle v_{n}}v私{\displaystyle v_{i}}

と の両方に接続する辺をとします。実数値の重み関数、および無向（単純）グラフが与えられている場合、 からへの最短経路は、すべての可能な経路にわたって の合計を最小化する経路（ただしおよび）です。グラフの各辺が単位重み または のとき、これは辺が最も少ない経路を見つけることに相当します。 E＝{e私、j}{\displaystyle E=\{e_{i,j}\}}e私、j{\displaystyle e_{i,j}}v私{\displaystyle v_{i}}vj{\displaystyle v_{j}}f:E→R{\displaystyle f:E\rightarrow\mathbb{R}}G{\displaystyle G}v{\displaystyle v}v′{\displaystyle v'}P＝（v1、v2、…、vn）{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}v1＝v{\displaystyle v_{1}=v}vn＝v′{\displaystyle v_{n}=v'}n{\displaystyle n}∑私＝1n−1f（e私、私+1）。{\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}f:E→{1}{\displaystyle f:E\rightarrow \{1\}}

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

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

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

アルゴリズム

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

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

単一ソース最短経路

無向グラフ

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

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

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

有向非巡回グラフ

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

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

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

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

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

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

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

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

重量アルゴリズム時間計算量著者
Z{\displaystyle \mathbb {Z} }お（EVログ⁡北）{\displaystyle O(E{\sqrt {V}}\log {N})}アンドリュー・V・ゴールドバーグ

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

重量アルゴリズム時間計算量著者
R≥0{\displaystyle \mathbb {R} _{\geq 0}}お（V）{\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 4 )でした。

無向グラフ

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

有向グラフ

重量時間計算量アルゴリズム
R{\displaystyle \mathbb {R} }（負のサイクルはありません）お（V3）{\displaystyle O(V^{3})}フロイド・ワーシャルアルゴリズム
北{\displaystyle \mathbb {N} }お（V3/2Ω（ログ⁡V）1/2）{\displaystyle O(V^{3}/2^{\オメガ (\log V)^{1/2}})}ウィリアムズ 2014
R{\displaystyle \mathbb {R} }（負のサイクルはありません）お（V2.5ログ2⁡V）{\displaystyle O(V^{2.5}\log ^{2}{V})}量子探索[ 10 ] [ 11 ]
R{\displaystyle \mathbb {R} }（負のサイクルはありません）O ( EV  +  V 2  log  V )ジョンソン・ダイクストラ
R{\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 ]他に使用されている技術は次のとおりです。

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

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

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

制約付きパス

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

部分的な観測可能性

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

戦略的最短経路

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

負のサイクル検出

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

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

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

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

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

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

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

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

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

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

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

参照

参考文献

注記

  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. ^ 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. ^ a b 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. ^ Chen, Danny Z. (1996年12月). 「幾何学的経路計画問題のためのアルゴリズムとソフトウェアの開発」. ACM Computing Surveys . 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 「道路網における最短経路のためのハブベースラベリングアルゴリズム」 Symposium on Experimental Algorithms、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. ^ Bar-Noy, Amotz; Schieber, 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章 経路問題のための評価代数」. Generic Inference: A Unifying Theory for Automated Reasoning . 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) 64020: 25– 37. doi : 10.1504/IJOR.2014.064020 .
  31. ^ Olya, Mohammad Hessam (2014). 「正規確率分布弧長を持つ一般最短経路問題へのダイクストラ法の適用」. International Journal of Operational Research . 21 (2) 64541: 143– 154. doi : 10.1504/IJOR.2014.064541 .

参考文献

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Shortest_path_problem&oldid=1335746576」より取得