ダイクストラ法

ダイクストラ法（/ˈdaɪk.strəz/ 、ダイクストラ）は、重み付きグラフ（例えば道路網を表す）のノード間の最短経路を見つけるためのアルゴリズムです。これは、コンピュータ科学者のエドガー・W・ダイクストラによって1956年に考案され、3年後に発表されました。^[⁴^]^[⁵^]^[⁶^]

ダイクストラ法は、与えられた始点ノードから他のすべてのノードへの最短経路を見つけます。^{[ 7 ]}^{: 196–206}最短経路が決定された後にアルゴリズムを終了することで、特定の宛先ノードへの最短経路を見つけるために使用できます。たとえば、グラフのノードが都市を表し、エッジのコストが直接道路で接続された都市のペア間の距離を表す場合、ダイクストラ法を使用して、1 つの都市と他のすべての都市間の最短経路を見つけることができます。最短経路アルゴリズムの一般的なアプリケーションは、ネットワークルーティングプロトコルであり、最も有名なのはIS-IS (Intermediate System to Intermediate System) とOSPF (Open Shortest Path First) です。また、ジョンソン法などのアルゴリズムのサブルーチンとしても使用されます。

このアルゴリズムは、これまでに知られている最短経路を選択するために、最小優先度キューのデータ構造を使用します。より高度な優先度キュー構造が発見される前は、ダイクストラの元のアルゴリズムは、 $\Theta (|V|^{2})$ 時間、 $|V|$ はノードの数です。^{[ 8 ]}^{[ 9 ]} Fredman & Tarjan 1984 は、実行時間の複雑さを最適化するためにフィボナッチヒープ優先度キューを提案しました。 $\Theta (|E|+|V|\log |V|)$ 、どこ $|E|$ はエッジの数です。これは、非負の重みが無制限の任意の有向グラフに対して、漸近的に知られている最速の単一始点最短経路アルゴリズムです。ただし、特殊なケース（重みが制限されている/整数である場合、有向非巡回グラフなど）では、さらに改善できます。前処理が可能な場合、縮約階層などのアルゴリズムは最大で7桁高速化できます。

ダイクストラ法は、エッジの重みが正の整数または実数であるグラフで一般的に使用されます。エッジの重みが部分的に順序付けられている任意のグラフに一般化できます。ただし、後続のラベル（エッジをたどると後続のラベルが生成されます）が単調非減少である必要があります。^{[ 10 ]}^{[ 11 ]}

多くの分野、特に人工知能では、ダイクストラ法またはその変種は均一なコスト探索を提供し、より一般的な最良優先探索の考え方の一例として定式化されている。^{[ 12 ]}

歴史

ロッテルダムからフローニンゲンへの最短移動経路は何か、一般的に言えば、ある都市からある都市への最短移動経路とは何か。これは私が約20分で設計した最短経路アルゴリズムです。ある朝、若い婚約者とアムステルダムで買い物をしていたとき、疲れてカフェのテラスに座ってコーヒーを飲んでいると、これをできるかどうか考えていたところ、最短経路アルゴリズムを設計しました。先ほども言ったように、20分で発明したものです。実際には、3年後の1959年に発表されました。その出版物は今でも読むことができ、実際、とても素晴らしいものです。素晴らしい理由の1つは、鉛筆と紙を使わずに設計したことです。後に、鉛筆と紙を使わずに設計することの利点の1つは、避けられる複雑さをほぼすべて避けざるを得ないことだと知りました。最終的に、そのアルゴリズムは、私にとって非常に驚くべきことに、私の名声の礎の1つとなりました。

—エドガー・ダイクストラ、フィリップ・L・フラナとのインタビュー、Communications of the ACM、2001年^{[ 5 ]}

ダイクストラは、1956年にアムステルダムの数学センターでプログラマーとして働いていたときに最短経路問題について考えました。彼は新しいARMACコンピュータの能力を実証したかったのです。^{[ 13 ]}彼の目的は、コンピュータに詳しくない人でも理解できる問題とコンピュータによる解決策を選ぶことでした。彼は最短経路アルゴリズムを設計し、後にそれをARMACに実装して、オランダの64都市のやや簡略化された交通マップに適用しました（都市番号をエンコードするのに6ビットで十分になるように、64に限定しました）。^{[ 5 ]} 1年後、彼は研究所の次のコンピュータに取り組んでいるハードウェアエンジニアが提起した別の問題に出会いました。それは、マシンの背面パネルのピンを接続するために必要なワイヤの量を最小限に抑えることでした。解決策として、彼はプリムの最小全域木アルゴリズムを再発見しました（これは以前ヤルニクによって知られており、プリムによっても再発見されました）。^{[ 14 ]}^{[ 15 ]}ダイクストラは、プリムの2年後、ヤルニクの29年後の1959年にこのアルゴリズムを発表した。^{[ 16 ]}^{[ 17 ]}

アルゴリズム

ロボットの動作計画問題において、開始ノード（左下、赤）から目標ノード（右上、緑）までの経路を見つけるダイクストラ法の図解。開いたノードは「暫定」ノード群（未訪問ノード群とも呼ばれる）を表す。塗りつぶされたノードは訪問済みのノードで、色は距離を表し、赤みが強いほど（開始ノードに）近い。ダイクストラ法はこれまでに知られている最短経路を選択するというヒューリスティックを用いるため、あらゆる方向のノードが均等に探索され、ほぼ円形の波面のように見える。

このアルゴリズムは開始ノードを必要とし、その開始ノードから他のすべてのノードまでの最短距離を計算します。ダイクストラ法は無限の距離から始まり、段階的に距離を改善しようとします。

未訪問ノードの集合を作成します。これが未訪問ノード集合です。
各ノードに開始点からの距離値を割り当てます。開始ノードの場合はゼロ、その他のノードの場合は、初期状態ではこれらのノードへのパスが知られていないため、無限大とします。実行中、ノードNの距離は、開始ノードとNの間でこれまでに発見された最短パスの長さになります。^{[ 18 ]}
未訪問ノードの集合から、距離が最小（有限）のノードを現在のノードとして選択します。初期状態では、これが開始ノード（距離ゼロ）となります。未訪問ノードの集合が空であるか、無限距離のノード（到達不可能なノード）のみを含む場合は、ステップ6にスキップしてアルゴリズムを終了します。対象ノードへのパスのみが関心事である場合は、現在のノードが対象ノードになった時点でアルゴリズムを終了します。そうでない場合は、アルゴリズムを続行します。
現在のノードについて、未訪問の隣接ノードをすべて考慮し、現在のノードを経由する距離を更新します。新しく計算された距離を、隣接ノードに現在割り当てられている距離と比較し、小さい方の距離を割り当てます。たとえば、現在のノードAに距離6が割り当てられており、隣接ノードBとの接続エッジの長さが2の場合、 Aを経由するBまでの距離は6 + 2 = 8となります。Bに以前8より大きい距離が割り当てられていた場合は、8に更新します（Aを経由するBへの経路の方が短いため）。そうでない場合は、現在の距離を維持します（Aを経由するBへの経路は最短ではないため）。
現在のノードの未訪問の隣接ノードをすべて考慮した後、現在のノードは未訪問ノードの集合から削除されます。したがって、訪問済みのノードは再チェックされません。これは、現在のノードで記録された距離が最小値（ステップ3で確認済み）であり、最終的な値であるため、正しい結果です。ステップ3から繰り返します。
ループが終了すると（ステップ3～5）、訪問したすべてのノードには、開始ノードからの最短距離が格納されます。

説明

都市地図上の2つの交差点間の最短経路は、鉛筆と紙を使ったこのアルゴリズムで見つけることができます。各交差点は別々の行にリストされます。1つは開始点であり、距離が0とラベル付けされます。他のすべての交差点は、最初は距離が無限大とラベル付けされます。これは、これらの交差点への経路がまだ確立されていないことを示すためです。各反復で、1つの交差点が現在の交差点になります。最初の反復では、これが開始点になります。

現在の交差点から、隣接する（直接接続されている）すべての交差点までの距離は、現在の交差点のラベル（値）と隣接交差点までの距離を合計し、その合計と隣接交差点の既存のラベルのうち小さい方の値で隣接交差点のラベルを書き換えることによって評価されます。つまり、現在の交差点を通る隣接交差点への経路が以前に評価された経路よりも短い場合、隣接交差点のラベルが書き換えられます。その場合、隣接交差点への経路に矢印を付け、隣接交差点を指し示す他の矢印をすべて消去します。現在の交差点の各隣接交差点までの距離が評価された後、現在の交差点は訪問済みとしてマークされます。ラベルが最小の未訪問の交差点が現在の交差点となり、目的地のラベルよりも小さいラベルを持つすべてのノードが訪問されるまで、このプロセスが繰り返されます。

未訪問のノードのうち、宛先のラベルよりも小さいラベルを持つノードがなくなると、残りの矢印が最短経路を示す。

擬似コード

次の擬似コードでは、dist はソースから他の頂点までの現在の距離を含む配列です。つまり、 dist[ u ]はソースから頂点uまでの現在の距離です。prev配列には、ソースから指定された頂点までの最短パス上の前のホップのノードへのポインタが含まれています (つまり、指定された頂点からソースまでのパス上の次のホップです)。コードu ← vertex in Q with min dist[u] は、 dist[ u ]の値が最小の頂点u を頂点セットQ内で検索します。Graph.Distance ( u , v )は、2 つの隣接ノードuとvを結ぶエッジの長さ (つまり、それらの間の距離) を返します。14 行目の変数altは、ソースノードから隣接ノードvまでのパスがu を経由する場合の長さです。この経路がvに対して記録されている現在の最短経路よりも短い場合、 vの距離はaltに更新されます。^[⁷^]

ユークリッド距離に基づくダイクストラ法のデモ。赤い線は最短経路カバー、つまりuと prev[ *u ] を結びます。青い線は緩和が行われる場所、つまりv を*Q内のノード*uに接続し、ソースから*vまでのより短い経路が得られる場所を示します。

1 関数Dijkstra( Graph , source ): 2 Graph.Verticesの各頂点vに対して 3 : 4 dist[ v ] ← 無限大 5 前へ[ v ] ← 未定義 6 vをQに追加 7 dist[ソース] ← 0 8 9 Qが空でない間: 10 u ← Q内の最小距離[u]を持つ頂点 11 Q.remove(u) 12 グラフ内の各エッジ(u, v)について 13 ： 14 alt ← dist[ u ] + Graph.Distance( u , v ) 15 もしalt < dist[ v ] ならば: 16 dist[ v ] ← alt 17 prev[ v ] ← u 18 19 戻り値 dist[], prev[]

頂点sourceとtarget間の最短経路を見つけるには、 u = targetの場合、 10 行目で探索を終了します。source からtargetへの最短経路は、逆反復によって得られます。

1 S ← 空のシーケンス 2 u ← target 3 if prev[ u ] is defined or u = source : // 頂点に到達可能であれば続行 4 while u is defined: // スタック S を使用して最短経路を構築 5 S.push(u) // 頂点をスタックにプッシュ 6 u ← prev[ u ] // target から source へトラバース

ここで、シーケンスSは、始点から終点までの最短経路の1つを構成する頂点のリストであり、経路が存在しない場合は空のシーケンスです。

より一般的な問題は、ソースとターゲット間の最短パスをすべて見つけることです（同じ長さのパスが複数存在する可能性があります）。次に、prev[]の各エントリに単一のノードのみを格納する代わりに、緩和条件を満たすすべてのノードを格納できます。たとえば、rとソースの両方がターゲットに接続し、ターゲットを通る異なる最短パス上にある場合（エッジのコストがどちらの場合も同じであるため）、rとソースの両方がprev[ target ]に追加されます。アルゴリズムが完了すると、prev[]データ構造は、元のグラフから一部のエッジが削除された部分集合であるグラフを記述します。その重要な特性は、アルゴリズムが何らかの開始ノードで実行された場合、そのノードから新しいグラフ内の他の任意のノードへのすべてのパスが、それらのノード間の最短パスであり、元のグラフからのその長さのすべてのパスが新しいグラフに存在することです。次に、実際に 2 つの指定されたノード間のこれらの最短パスをすべて見つけるには、深さ優先探索などの新しいグラフ上のパス探索アルゴリズムが機能します。

優先度キューを使用する

最小優先度キューは、add_with_priority()、decrease_priority()、extract_min() という3 つの基本操作を提供する抽象データ型です。前述のように、このようなデータ構造を使用すると、基本的なキューを使用する場合よりも計算時間が短縮されます。特に、フィボナッチヒープ^[¹⁹^]やブローダルキューは、これら 3 つの操作に対して最適な実装を提供します。アルゴリズムは見た目が若干異なるため、ここでは擬似コードで別途実装します。

1 関数Dijkstra( Graph , source ): 2 Q ← 頂点優先度を格納するキュー 3 4 dist[ source ] ← 0 // 初期化 5 Q .add_with_priority( source , 0) // 関連付けられた優先度は dist[·] と等しい 6 7 各頂点vについてGraph.Vertices : 8 v ≠ sourceの場合 9 prev[ v ] ← UNDEFINED // v の先行要素 10 dist[ v ] ← INFINITY // source から v までの距離が不明 11 Q.add_with_priority(v, INFINITY) 12 13 14 while Q is not empty: // メインループ 15 u ← Q .extract_min() // 最適な頂点を削除して返す 16 for each edge (u, v) : // u のすべての v 近傍を走査する 17 alt ← dist[ u ] + Graph.Distance( u , v ) 18 もしalt < dist[ v ] ならば: 19 prev[ v ] ← u 20 dist[ v ] ← alt 21 Q .decrease_priority( v , alt ) 22 23 戻り値(距離、前）

初期化フェーズで優先度キューにすべてのノードを投入する代わりに、ソースのみを含むように初期化することも可能です。その場合、ブロック内でdecrease_priority()はadd_with_priority()操作になります。^[⁷^]^:¹⁹⁸ifalt < dist[v]

もう一つの選択肢は、ノードを無条件に優先度キューに追加し、抽出後に（）再訪問していないか、またはブロック内でより短い接続がまだ見つかっていないかを確認することです。これは、キューから関連する優先度を追加で抽出し、ループ内でのみさらに処理することで実現できます。^[²⁰^]u ← Q.extract_min()if alt < dist[v]pifp == dist[u]whileQ is not empty

これらの代替案では、キー減少機能のない完全に配列ベースの優先度キューを使用することができ、実際にはさらに高速な計算時間を実現できることがわかっています。ただし、グラフが密なほどパフォーマンスの差は小さくなることがわかっています。^{[ 21 ]}

証拠

ダイクストラ法の正しさを証明するために、訪問したノードの数に対して数学的帰納法を用いることができる。 ^{[ 22 ]}

不変仮説：訪問済みノードvごとに、は出発地からvまでの最短距離であり、未訪問ノードuごとに、は訪問済みノードのみを経由して移動する場合の出発地からuまでの最短距離、またはそのような経路が存在しない場合は無限大である。（注：は未訪問ノードの実際の最短距離であるとは仮定せず、は実際の最短距離であると仮定する。）dist[v]dist[u]dist[u]dist[v]

基本ケース

基本ケースは、訪問ノードが1つ（ソース）のみの場合です。負の重みは許容されないため、その距離はゼロと定義され、これが最短距離となります。したがって、仮説は成り立ちます。

誘導

仮説が成り立つと仮定すると $k$ 訪問したノード、それが成り立つことを示すために $k+1$ ノードをとします。次に訪問するノード、つまりが最小のノードをuとします。主張は、がソースからuまでの最短距離であるということです。dist[u]dist[u]

証明は背理法による。より短い経路が存在するならば、その短い経路には未訪問のノードが含まれているか、含まれていないかのどちらかである。

前者の場合、w をこの短いパス上の最初の未訪問ノードとする。帰納法により、ソースからuおよびwへの訪問済みノードを経由する最短パスのコストはそれぞれとのみである。これは、ソースからwを経由してuに行くコストは、少なくとも+ wからuに行く最小コストのコストであることを意味する。エッジのコストは正であるため、wからuに行く最小コストは正の数である。しかし、は最大でもである。そうでなければ、優先度キューによって u の代わりに w が選択されていたはずだからである。これは、+ 正の数 <であることが既に確立されているため、矛盾である。dist[u]dist[w]dist[w]dist[u]dist[w]dist[w]dist[u]
後者の場合、最短経路上の最後から2番目のノードをwとします。つまり、となります。これは矛盾です。なぜなら、 wが訪問される時点では、は最大でに設定されているはずだからです。dist[w] + Graph.Edges[w,u] < dist[u]dist[u]dist[w] + Graph.Edges[w,u]

他の訪問済みノードvについては、帰納的仮説により、ソースからの最短距離であることが既にわかっているため、これらの値は変更されません。dist[v]

uを処理した後も、未訪問のノードwごとに、訪問済みのノードのみを使用してソースからwまでの最短距離がであるという事実は変わりません。uを使用しないより短いパスは既に発見されており、u を使用したより短いパスは、 u の処理時に更新されています。dist[w]

すべてのノードを訪問した後、始点から任意のノードvへの最短経路は、訪問済みのノードのみで構成されます。したがって、が最短距離となります。dist[v]

実行時間

$エッジE$ と頂点 $V$ を持つグラフ上でのダイクストラ法の実行時間の上限は、エッジの数の関数として表すことができ、 $|E|$ 、頂点の数、 $|V|$ ビッグオー記法を使用。複雑度の上限は主に集合 $Q を表現するために使用されるデータ構造に依存します。以下では$ 、上限を簡略化できます。 $|E|$ は $O(|V|^{2})$ 任意の単純グラフに対しては、この単純化は、いくつかの問題では、他の上限が $|E|$ 保持する可能性がある。

頂点集合 $Q$ の任意のデータ構造の場合、実行時間は次のとおりです。^{[ 2 ]}

\Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),

どこ $T_{\mathrm {dk} }$ そして $T_{\mathrm {em} }$ $これらはそれぞれ、 Q$ におけるデクリメントキー操作と抽出ミニマム操作の複雑度です。

ダイクストラ法の最も単純なバージョンでは、頂点集合 $Q を$ リンクリストまたは配列として、エッジを隣接リストまたは行列として格納します。この場合、最小値抽出は単に $Q$ 内のすべての頂点に対する線形探索であるため、実行時間は ${\textstyle \シータ (|E|+|V|^{2})=\シータ (|V|^{2})}$ 。

疎なグラフ、つまり、 $\displaystyle |V|^{2}}$ エッジに関して、ダイクストラ法は、グラフを隣接リストの形式で格納し、自己平衡二分探索木、二分ヒープ、ペアリングヒープ、フィボナッチヒープ、または優先度ヒープを優先度キューとして使用して最小値の抽出を効率的に実装することで、より効率的に実装できます。二分ヒープでキー減少ステップを効率的に実行するには、各頂点をヒープ内の位置にマッピングする補助データ構造を使用し、優先度キュー $Q$ が変化するにつれてこの構造を更新する必要があります。自己平衡二分探索木または二分ヒープを使用する場合、アルゴリズムは ${\textstyle \Theta ((|E|+|V|)\log |V|)}$ 最悪の場合の時間。連結グラフの場合、この時間制限は次のように簡略化できます。 ${\textstyle \Theta (|E|\log |V|)}$ フィボナッチヒープはこれを改善し、 ${\textstyle \Theta (|E|+|V|\log |V|)}$ 。

バイナリヒープを使用する場合、平均時間計算量は最悪ケースよりも低くなります。エッジコストが共通の確率分布から独立に抽出されると仮定すると、キー減少操作の期待値は以下で制限されます。 $\Theta (|V|\log(|E|/|V|))$ 合計実行時間は^{[ 7 ]}^{： 199～200です。}

O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).

実用的な最適化と無限グラフ

ダイクストラ法の一般的な表現では、最初はすべてのノードが優先度キューに入力されます。しかし、これは必須ではありません。アルゴリズムは、1 つの項目のみを含む優先度キューから開始し、新しい項目が発見されるたびに挿入することができます (キーを減らす代わりに、キーがキューにあるかどうかを確認します。ある場合はキーを減らし、ない場合は挿入します)。^{[ 7 ]}^{: 198}このバリアントは、一般的なバリアントと同じ最悪の場合の境界を持ちますが、実際には優先度キューが小さくなるため、キュー操作が高速化されます。^{[ 12 ]}

さらに、グラフにすべてのノードを挿入しないことで、アルゴリズムを拡張して、無限グラフやメモリに表現するには大きすぎるグラフ上の、単一のソースからターゲットノードの集合のうち最も近いノードまでの最短経路を見つけることが可能になります。結果として得られるアルゴリズムは、人工知能の文献では均一コスト探索（UCS）と呼ばれ^{[ 12 ]}^{[ 23 ]}^{[ 24 ]}、擬似コードでは次のように表現できます。

手続きuniform_cost_search(start)は ノード ← 開始 フロンティア ← ノードのみを含む優先度キュー 展開済み ← 空集合  フロンティアが空の場合は 失敗を返す ノード ← frontier.pop() もしノードが目標状態であれば、 ソリューション(ノード)を返す。 expanded.add(node) 各ノードの隣接ノードnについて、nが拡張ノードでもフロンティアノードでもない場合は、 frontier.add( n ) を実行する。そうでない場合は、n がより高いコストでフロンティアノードに含まれている場合は、n を追加する。 既存のノードをnに置き換える

非常に大きなグラフの場合、その複雑さは別の方法で表現できます。C $* が$ $開始$ ノードから「目標」述語を満たす任意のノードまでの最短パスの長さであり、各エッジのコストが少なくとも $ε$ であり、ノードごとの隣接ノードの数が $b$ に制限されている場合、アルゴリズムの最悪ケースの時間計算量と空間計算量はどちらも $O (b 1+⌊ C * ⁄ ε ⌋)$ です。^{[ 23 ]}

単一ターゲットの場合のさらなる最適化には、双方向バリアント、 A* アルゴリズムなどの目標指向バリアント( § 関連問題とアルゴリズムを参照)、最短経路の中間セグメントを形成する可能性のあるノードを決定するためのグラフ剪定 (到達ベースルーティング)、および $s - t$ ルーティングを $s$ と $t$ をそれぞれの「トランジットノード」に接続し、その後「ハイウェイ」を使用してこれらのトランジットノード間の最短経路計算を行うように削減する入力グラフの階層的分解が含まれます。^{[ 25 ]}特定の問題で最適な実用的パフォーマンスを得るには、このような手法の組み合わせが必要になる場合があります。^{[ 26 ]}

双方向ダイクストラ

双方向ダイクストラ法は、すべての頂点ではなく、与えられた始点頂点 $s$ と終点頂点 $t$ の間の最短経路を効率的に計算するように設計されたダイクストラ法の変種です。重要なアイデアは、2 つの同時探索を実行することです。1 つは元のグラフ上の $sからの順方向探索、もう 1 つはエッジが反転したグラフ上の$ $t$ からの逆方向探索です。各探索は、独自の暫定的な距離推定値、優先度キュー、および「確定済み」頂点のセットを保持します。2 つのフロンティアは互いに近づき、最短の $s-t$ 経路上のどこかで出会います。^{[ 27 ]}

2 つの距離配列 $d f [v] ($ $sから$ $v$ までの距離) と $d b [v]$ ( $vから$ $t$ までの距離) が保持され、 $d$ $f$ $[$ $s$ $] = 0$ および $d$ $b$ $[$ $t$ $] = 0$ の場合を除き、すべて $\infty$ に初期化されます。2 つの優先度キュー $Q$ $f$ と $Q$ $b$ は、まだ完全に処理されていない頂点を保持し、2 つのセット $S$ $f$ と $S$ $b は$ 、各方向で最短経路距離が確定した頂点を格納します。変数 $μ は、$ これまでに見つかった最良の完全な $s-t$ 経路の長さを格納し、初期値は $\infty です$ 。

このアルゴリズムは、現在より小さいキーを持つキューから最小距離の頂点を繰り返し抽出し、その出力（または入力）エッジを緩和し、2つの確定済み集合間の接続が発見されるたびに $μを更新します。$

\mu \leftarrow \min(\mu ,\;d_{f}[u]+w(u,x)+d_{b}[x])

エッジをリラックスさせるとき

(u,x)

前方探索と

x\in S_{b}

、

そして、後方探索についても同様に同じことが言える。

重要な特徴は停止条件です。両方のキューの現在の最小優先度の合計が少なくとも $μ$ になると、まだ確定していないパスは $μ$ よりも改善できません。この時点で $μは$ 真の最短パス距離 $δ(s, t)$ に等しくなり、探索は終了します。^{[ 27 ]}

この基準を用いることで、2つの国境が接した時点で停止してしまうというよくある間違いを避けることができる。そうすると、別の場所でより短い代替ルートを見落としてしまう可能性があるからだ。

一般的なグラフでは、各検索で探索する範囲は探索空間の約半分程度で済むため、双方向ダイクストラ法は、単一ペアのクエリに対して一方向ダイクストラ法を用いる場合と比べて、訪問する頂点数や緩和するエッジ数がはるかに少なくて済むことが多い。道路網のようなグラフでは、その効果は劇的で、探索領域が指数関数的に大きな球体から、より小さな2つの半球体に縮小される場合もある。

この方法は、地図やナビゲーションソフトウェアのポイントツーポイントルーティングで広く使用されており、ALT、縮約階層、リーチベースルーティングなどの多くの高速化技術の基礎となっています。^{[ 28 ]}

実際の最短経路（距離だけでなく）が必要な場合は、両方の検索で先行ポインタを保存できます。μ が何らかの交差点 $x$ を介して更新されると、アルゴリズムはこの交差点を記録し、 $sから$ $x$ への順方向経路と $xから$ $t$ への逆方向経路を連結した最終経路を再構築します。

理論的な研究によると、最適化された双方向アプローチはインスタンス最適になり得る、つまり、同じグラフインスタンス上で漸近的に緩和できるエッジ数を減らす正しいアルゴリズムは存在しないということである。^{[ 29 ]}

実用性能に関する考慮事項

ダイクストラ法は非負のエッジ重みを持つグラフに対して最適ですが、実際の実行時間はデータ構造とグラフの特性の両方に依存します。バイナリヒープを使用すると、実行時間は O((V+E)logV) になります。フィボナッチヒープなどの代替手段は理論上の上限はより優れていますが、定数係数が大きいため、実際のアプリケーションではパフォーマンスが低下することがよくあります。^{[ 30 ]}

グラフ構造も重要な役割を果たします。道路地図のような疎なネットワークでは、ほとんどの頂点の次数が低いため、ダイクストラ法が効率的に動作します。密なグラフでは緩和が増加し、処理が遅くなります。このため、最新のルーティングシステムでは、ダイクストラ法をA*探索、ランドマークヒューリスティクス、縮約階層などの前処理方法と組み合わせて使用することが多く、これにより探索空間が大幅に削減されます。^{[ 31 ]}

メモリ局所性も重要な要素です。キャッシュ最適化された優先度キューと隣接レイアウトは、CPU キャッシュの制限を超える大規模グラフのレイテンシを削減できます。^{[ 32 ]}

こうした理由から、実際のシステムでは、特定のグラフの種類やハードウェアの制約に合わせて調整された、特殊なダイクストラ法の変種が使用されることが多い。

距離による比較ソートの最適性

ダイクストラ法は、単に距離や経路を計算するだけでなく、与えられた開始頂点からの距離に基づいて頂点をソートするためにも使用できます。2023年に、Haeupler、Rozhoň、Tětek、Hladík、およびTarjan（1984年のヒープの発明者の1人）は、正の重みを持つ有向グラフ上のこのソート問題に対して、特別なヒープデータ構造を持つダイクストラ法のバージョンの実行時間と比較回数が、同じグラフと開始頂点上の同じソート問題に対して可変エッジ重みを持つ比較ベースのアルゴリズムの中で最適値の定数倍以内であることを証明しました。これを実現するために、彼らは、ヒープから最小要素を返す/削除するコストが、ヒープ内の要素数ではなく、その後に挿入された要素数に対して対数となる比較ベースのヒープを使用しています。^{[ 33 ]}^{[ 34 ]}

特殊派生型

弧の重みが小さな整数である場合（パラメータによって制限される） $C$ ）速度向上のために専用キューを使用できる。この種の最初のアルゴリズムは、正の整数エッジ重みを持つグラフに対するDial のアルゴリズム^{[ 35 ]}であり、バケットキューを使用して実行時間を取得する。 $O(|E|+|V|C)$ 優先度キューとしてヴァン・エムデ・ボアス木を使用すると、複雑さが $O(|E|+|V|\log C/\log \log |V|C)$ ^{[ 36 ]}新しい基数ヒープとよく知られたフィボナッチヒープを組み合わせた別の興味深いバリアントは、 $O(|E|+|V|{\sqrt {\log C}})$ ^{[ 36 ]}最後に、この特殊なケースにおける最良のアルゴリズムは、 $O(|E|\log \log |V|)$ ^{[ 37 ]}時間と $O(|E|+|V|\min\{(\log |V|)^{1/3+\バレプシロン },(\log C)^{1/4+\バレプシロン }\})$ 時間。^{[ 38 ]}

注記

↑議論の余地あり。Moshe Sniedovich (2006) 「ダイクストラのアルゴリズム再考：動的計画法との関連」 Control and Cybernetics 35 : 599–620を参照。そして下部。
1 2 Cormen et al. 2001 .
1 2 Fredman & Tarjan 1987 .
↑ Richards, Hamilton. "Edsger Wybe Dijkstra" . AM Turing Award . Association for Computing Machinery . 2017 年10 月 16 日取得.数学センターでは、ARMAC コンピュータの構築が主要なプロジェクトでした。1956 年の公式開所式のために、ダイクストラは、非技術者にとって興味深い問題を解決するプログラムを考案しました。都市を結ぶ道路網が与えられたとき、指定された 2 つの都市間の最短ルートは何か?
1 2 3 Frana, Phil (2010 年 8 月) 「Edsger W. Dijkstra 氏へのインタビュー」Communications of the ACM . 53 (8): 41– 47. doi : 10.1145/1787234.1787249 . S2CID 27009702 .
↑ダイクストラ、EW (1959)。「グラフに関連した 2 つの問題に関するメモ」(PDF)。数学。1 : 269–271。CiteSeerX 10.1.1.165.7577。土井：10.1007/BF01386390。S2CID 123284777。
1 2 3 4 5 Mehlhorn, Kurt ; Sanders, Peter (2008). "第 10 章最短経路" (PDF) .アルゴリズムとデータ構造: 基本ツールボックス. Springer. doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3。
↑ Schrijver, Alexander (2012). 「最短経路問題の歴史について」（PDF） . Optimization Stories . Documenta Mathematica Series. Vol. 6. pp. 155–167 . doi : 10.4171/dms/6/19 . ISBN 978-3-936609-58-5。
↑ Leyzorek et al. 1957 .
↑シュチェジニアク、イレノイシュ。ヤイシュチク、アンジェイ;ウォナ＝シュチェジニアク、ボジェナ（2019）。「光ネットワーク用の汎用ダイクストラ」。光通信とネットワーキングのジャーナル。11 (11): 568–577 . arXiv : 1810.04481。土井: 10.1364/JOCN.11.000568。S2CID 52958911。
↑シュチェジニアク、イレノイシュ。 Woźna-Szcześniak、Bożena (2023)、「Generic Dijkstra: Correctness and tractability」、NOMS 2023-2023 IEEE/IFIP Network Operations and Management Symposium、pp. 1–7、arXiv : 2204.13547、doi : 10.1109/NOMS56928.2023.10154322、ISBN 978-1-6654-7716-1S2CID 248427020
1 2 3 Felner, Ariel (2011). Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm . Proc. 4th Int'l Symp. on Combinatorial Search. Archived from the original on 18 February 2020 . Retrieved 12 February 2015 .経路探索問題において、フェルナーはキューのサイズを500～600分の1に縮小でき、実行時間を約40%削減できることを発見した。
↑ 「ARMAC」。オランダのコンピュータ史における知られざる英雄たち。2007年。 2013年11月13日にオリジナルからアーカイブ済み。
↑ダイクストラ、エドガー・W.、「グラフに関連する2つの問題に関する考察（PDF）」
↑ Tarjan, Robert Endre (1983), Data Structures and Network Algorithms , CBMS_NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, p. 75, 3 番目の古典的な最小全域木アルゴリズムは Jarník によって発見され、Prim と Dikstra によって再発見されました。これは一般に Prim のアルゴリズムとして知られています。
↑ Prim, RC (1957). "最短接続ネットワークといくつかの一般化" (PDF) . Bell System Technical Journal . 36 (6): 1389– 1401. Bibcode : 1957BSTJ...36.1389P . doi : 10.1002/j.1538-7305.1957.tb01515.x . 2017年7月18日にオリジナル(PDF)からアーカイブ済み。 2017年7月18日に取得。
↑ V. Jarník: O jistém problému minimálním [ある最小限の問題について]、Práce Moravské Přírodovědecké Společnosti、6、1930、57–63 ページ。 (チェコ語で)
↑ Gass, Saul; Fu, Michael (2013). "Dijkstra's Algorithm".In Gass, Saul I; Fu, Michael C (eds.). Encyclopedia of Operations Research and Management Science . Vol. 1. Springer. doi : 10.1007/978-1-4419-1153-7 . ISBN 978-1-4419-1137-7– Springer Link経由。
↑フレッドマン&タージャン 1984。
↑キューの更新時にdist[ v ] ← altが更新されるため、 p < dist[ u ]は決して成立しないことに注意してください。議論については、 https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-keyを参照してください。
↑ Chen, M.; Chowdhury, RA; Ramachandran, V.; Roche, DL; Tong, L. (2007). Priority Queues and Dijkstra's Algorithm – UTCS Technical Report TR-07-54 – 12 October 2007 (PDF) . Austin, Texas: The University of Texas at Austin, Department of Computer Sciences.
↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2022) [1990]. "22".アルゴリズム入門（第4版）. MIT Press and McGraw-Hill. pp. 622–623 . ISBN 0-262-04630-X。
1 2 Russell, Stuart ; Norvig, Peter (2009) [1995].人工知能：現代的アプローチ（第3版）. Prentice Hall. pp. 75, 81. ISBN 978-0-13-604259-4。
↑最小コスト優先探索とも呼ばれる: Nau, Dana S. (1983). "Expert computer systems" (PDF) . Computer . 16 (2). IEEE: 63– 85. doi : 10.1109/mc.1983.1654302 . S2CID 7301753 .
↑ Wagner, Dorothea; Willhalm, Thomas (2007).最短経路計算の高速化手法. STACS. pp. 23–36 .
↑バウアー、ラインハルト。デリング、ダニエル。サンダース、ピーター。デニス・シーファーデッカー。シュルテス、ドミニク。ワーグナー、ドロテア (2010)。「ダイクストラのアルゴリズムに対する階層的および目標指向の高速化手法の組み合わせ」。ACM 実験アルゴリズムジャーナル。15 : 2.1.土井: 10.1145/1671970.1671976。S2CID 1661292。
1 2 Thomas, Mark (2020年5月30日). "双方向ダイクストラ" . UCL数学ブログ. 2025年10月3日取得。
↑ Goldberg, Andrew V.; Harrelson, Chris (2005).最短経路の計算: A* 探索とグラフ理論の融合. 第 16 回 ACM–SIAM 離散アルゴリズムシンポジウム (SODA) 論文集.
↑ハウプラー、ベルンハルト。フラディク、リチャード。ロゾン、ヴァーツラフ。ロバート・E・タージャン;テテク、ヤクブ（2025）。「双方向ダイクストラのアルゴリズムはインスタンス最適化です。」イオアナ・オリアナのベルセアにて。パー、ラスムス（編）。2025 アルゴリズムのシンプルさに関するシンポジウム、SOSA 2025、米国ルイジアナ州ニューオーリンズ、2025 年 1 月 13 ～ 15 日。工業および応用数学協会。ページ202–215。arXiv : 2410.14638。土井: 10.1137/1.9781611978315.16。
↑コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009)。アルゴリズム入門(第 3版)。 MITプレス。658–663ページ。
↑ Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Delling, Daniel (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks . Experimental Algorithms (WEA 2008). Lecture Notes in Computer Science. Vol. 5038. Springer. pp. 319–333 . doi : 10.1007/978-3-540-68552-4_24 . ISBN 978-3-540-68548-7。
↑サンダース、ピーター。シュルテス、ドミニク (2005)。ハイウェイ階層により、正確な最短パスのクエリが迅速化されます。アルゴリズム – ESA 2005。コンピュータサイエンスの講義ノート。 Vol. 3669.スプリンガー。 pp. 568–579 .土井: 10.1007/11561071_51。ISBN 978-3-540-29118-3。
↑ハウプラー、ベルンハルト。フラディク、リチャード。ロジョニ、ヴァーツラフ。ロバート・タージャン。テクテク、ヤクブ（2024年10月28日）。「最悪ケースを超えたヒープによるダイクストラの普遍的最適性」。arXiv : 2311.11793 [ cs.DS ]。
↑ Brubaker, Ben (2024年10月25日). 「コンピュータ科学者がグラフを走査する最良の方法を確立」 . Quanta Magazine . 2024年12月9日取得.
↑ 1969 にダイヤルしてください。
1 2 Ahuja et al. 1990 .
↑ソーラップ 2000。
↑ラマン 1997。
↑ Sniedovich, M. (2006). "Dijkstraのアルゴリズムの再検討：動的計画法との関連" (PDF) . Journal of Control and Cybernetics . 35 (3): 599– 620.インタラクティブな計算モジュールを備えた論文のオンライン版。
↑ Denardo, EV (2003).動的計画法：モデルと応用. ミネオラ、ニューヨーク：ドーバー出版. ISBN 978-0-486-42810-9。
↑スニエドヴィッチ、M. (2010).動的計画法：基礎と原理.フランシス＆テイラー. ISBN 978-0-8247-4099-3。
↑ダイクストラ 1959、p. 270。

参考文献

トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。「セクション 24.3: ダイクストラのアルゴリズム」。アルゴリズム入門(第 2 版)。MIT PressとMcGraw–Hill。ページ595–601。ISBN 0-262-03293-7。
Dial, Robert B. (1969). "アルゴリズム 360: 位相順序付け付き最短経路フォレスト[ H ] " . Communications of the ACM . 12 (11): 632– 633. doi : 10.1145/363269.363610 . S2CID 6754003 .
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 .
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 .
Zhan, F. Benjamin; Noon, Charles E. (1998年2月)「最短経路アルゴリズム：実際の道路ネットワークを用いた評価」Transportation Science . 32 (1): 65–73 . doi : 10.1287/trsc.32.1.65 . S2CID 14986297 .
Leyzorek, M.; Gray, RS; Johnson, AA; Ladew, WC; Meaker, Jr., SR; Petry, RM; Seitz, RN (1957).モデル技術の調査 – 第1回年次報告書 – 1956年6月6日～1957年7月1日 – 通信システムのためのモデル技術の研究。オハイオ州クリーブランド：ケース工科大学。
Knuth, DE (1977). "ダイクストラ法の一般化". Information Processing Letters . 6 (1): 1– 5. doi : 10.1016/0020-0190(77)90002-3 .
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (1990 年 4 月). "最短経路問題のためのより高速なアルゴリズム" (PDF) . Journal of the ACM . 37 (2): 213– 223. doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589 .
Raman, Rajeev (1997). 「単一始点最短経路問題に関する最近の結果」 . SIGACT News . 28 (2): 81– 87. doi : 10.1145/261342.261352 . S2CID 18031586 .
ソープ、ミッケル (2000)。「RAM 優先キュー」。SIAM ジャーナルオンコンピューティング。30 (1): 86–109。土井: 10.1137/S0097539795288246。S2CID 5221089。
Thorup, Mikkel (1999). "線形時間で正の整数重みを持つ無向単一始点最短経路" . Journal of the ACM . 46 (3): 362–394 . doi : 10.1145/316542.316548 . S2CID 207654795 .

外部リンク

エドガー・W・ダイクストラ氏（ミネソタ大学ミネアポリス校チャールズ・バベッジ研究所）へのオーラルヒストリーインタビュー
ダイクストラ法のTDDによる実装、ロバート・セシル・マーティン、クリーンコードブログ

[1] 議論の余地あり。Moshe Sniedovich (2006) 「ダイクストラのアルゴリズム再考：動的計画法との関連」 Control and Cybernetics 35 : 599–620を参照。そして下部。

[FOOTNOTECormenLeisersonRivestStein2001-2] 1 2 Cormen et al. 2001 .

[FOOTNOTEFredmanTarjan1987-3] 1 2 Fredman & Tarjan 1987 .

[4] Richards, Hamilton. "Edsger Wybe Dijkstra" . AM Turing Award . Association for Computing Machinery . 2017 年10 月 16 日取得.数学センターでは、ARMAC コンピュータの構築が主要なプロジェクトでした。1956 年の公式開所式のために、ダイクストラは、非技術者にとって興味深い問題を解決するプログラムを考案しました。都市を結ぶ道路網が与えられたとき、指定された 2 つの都市間の最短ルートは何か?

[Dijkstra_Interview2-5] 1 2 3 Frana, Phil (2010 年 8 月) 「Edsger W. Dijkstra 氏へのインタビュー」Communications of the ACM . 53 (8): 41– 47. doi : 10.1145/1787234.1787249 . S2CID 27009702 .

[Dijkstra19592-6] ダイクストラ、EW (1959)。「グラフに関連した 2 つの問題に関するメモ」(PDF)。数学。1 : 269–271。CiteSeerX 10.1.1.165.7577。土井：10.1007/BF01386390。S2CID 123284777。

[mehlhorn-7] 1 2 3 4 5 Mehlhorn, Kurt ; Sanders, Peter (2008). "第 10 章最短経路" (PDF) .アルゴリズムとデータ構造: 基本ツールボックス. Springer. doi : 10.1007/978-3-540-77978-0 . ISBN 978-3-540-77977-3。

[8] Schrijver, Alexander (2012). 「最短経路問題の歴史について」（PDF） . Optimization Stories . Documenta Mathematica Series. Vol. 6. pp. 155–167 . doi : 10.4171/dms/6/19 . ISBN 978-3-936609-58-5。

[FOOTNOTELeyzorekGrayJohnsonLadew1957-9] Leyzorek et al. 1957 .

[Generic_Dijkstra2-10] シュチェジニアク、イレノイシュ。ヤイシュチク、アンジェイ;ウォナ＝シュチェジニアク、ボジェナ（2019）。「光ネットワーク用の汎用ダイクストラ」。光通信とネットワーキングのジャーナル。11 (11): 568–577 . arXiv : 1810.04481。土井: 10.1364/JOCN.11.000568。S2CID 52958911。

[Generic_Dijkstra_correctness2-11] シュチェジニアク、イレノイシュ。 Woźna-Szcześniak、Bożena (2023)、「Generic Dijkstra: Correctness and tractability」、NOMS 2023-2023 IEEE/IFIP Network Operations and Management Symposium、pp. 1–7、arXiv : 2204.13547、doi : 10.1109/NOMS56928.2023.10154322、ISBN 978-1-6654-7716-1S2CID 248427020

[felner-12] 1 2 3 Felner, Ariel (2011). Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm . Proc. 4th Int'l Symp. on Combinatorial Search. Archived from the original on 18 February 2020 . Retrieved 12 February 2015 .経路探索問題において、フェルナーはキューのサイズを500～600分の1に縮小でき、実行時間を約40%削減できることを発見した。

[13] 「ARMAC」。オランダのコンピュータ史における知られざる英雄たち。2007年。 2013年11月13日にオリジナルからアーカイブ済み。

[EWD841a2-14] ダイクストラ、エドガー・W.、「グラフに関連する2つの問題に関する考察（PDF）」

[15] Tarjan, Robert Endre (1983), Data Structures and Network Algorithms , CBMS_NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, p. 75, 3 番目の古典的な最小全域木アルゴリズムは Jarník によって発見され、Prim と Dikstra によって再発見されました。これは一般に Prim のアルゴリズムとして知られています。

[16] Prim, RC (1957). "最短接続ネットワークといくつかの一般化" (PDF) . Bell System Technical Journal . 36 (6): 1389– 1401. Bibcode : 1957BSTJ...36.1389P . doi : 10.1002/j.1538-7305.1957.tb01515.x . 2017年7月18日にオリジナル(PDF)からアーカイブ済み。 2017年7月18日に取得。

[17] V. Jarník: O jistém problému minimálním [ある最小限の問題について]、Práce Moravské Přírodovědecké Společnosti、6、1930、57–63 ページ。 (チェコ語で)

[18] Gass, Saul; Fu, Michael (2013). "Dijkstra's Algorithm".In Gass, Saul I; Fu, Michael C (eds.). Encyclopedia of Operations Research and Management Science . Vol. 1. Springer. doi : 10.1007/978-1-4419-1153-7 . ISBN 978-1-4419-1137-7– Springer Link経由。

[FOOTNOTEFredmanTarjan1984-19] フレッドマン&タージャン 1984。

[Note2-20] キューの更新時にdist[ v ] ← altが更新されるため、 p < dist[ u ]は決して成立しないことに注意してください。議論については、 https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-keyを参照してください。

[chen_072-21] Chen, M.; Chowdhury, RA; Ramachandran, V.; Roche, DL; Tong, L. (2007). Priority Queues and Dijkstra's Algorithm – UTCS Technical Report TR-07-54 – 12 October 2007 (PDF) . Austin, Texas: The University of Texas at Austin, Department of Computer Sciences.

[22] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2022) [1990]. "22".アルゴリズム入門（第4版）. MIT Press and McGraw-Hill. pp. 622–623 . ISBN 0-262-04630-X。

[aima-23] 1 2 Russell, Stuart ; Norvig, Peter (2009) [1995].人工知能：現代的アプローチ（第3版）. Prentice Hall. pp. 75, 81. ISBN 978-0-13-604259-4。

[24] 最小コスト優先探索とも呼ばれる: Nau, Dana S. (1983). "Expert computer systems" (PDF) . Computer . 16 (2). IEEE: 63– 85. doi : 10.1109/mc.1983.1654302 . S2CID 7301753 .

[speedup2-25] Wagner, Dorothea; Willhalm, Thomas (2007).最短経路計算の高速化手法. STACS. pp. 23–36 .

[26] バウアー、ラインハルト。デリング、ダニエル。サンダース、ピーター。デニス・シーファーデッカー。シュルテス、ドミニク。ワーグナー、ドロテア (2010)。「ダイクストラのアルゴリズムに対する階層的および目標指向の高速化手法の組み合わせ」。ACM 実験アルゴリズムジャーナル。15 : 2.1.土井: 10.1145/1671970.1671976。S2CID 1661292。

[UCL-27] 1 2 Thomas, Mark (2020年5月30日). "双方向ダイクストラ" . UCL数学ブログ. 2025年10月3日取得。

[28] Goldberg, Andrew V.; Harrelson, Chris (2005).最短経路の計算: A* 探索とグラフ理論の融合. 第 16 回 ACM–SIAM 離散アルゴリズムシンポジウム (SODA) 論文集.

[29] ハウプラー、ベルンハルト。フラディク、リチャード。ロゾン、ヴァーツラフ。ロバート・E・タージャン;テテク、ヤクブ（2025）。「双方向ダイクストラのアルゴリズムはインスタンス最適化です。」イオアナ・オリアナのベルセアにて。パー、ラスムス（編）。2025 アルゴリズムのシンプルさに関するシンポジウム、SOSA 2025、米国ルイジアナ州ニューオーリンズ、2025 年 1 月 13 ～ 15 日。工業および応用数学協会。ページ202–215。arXiv : 2410.14638。土井: 10.1137/1.9781611978315.16。

[30] コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009)。アルゴリズム入門(第 3版)。 MITプレス。658–663ページ。

[31] Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Delling, Daniel (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks . Experimental Algorithms (WEA 2008). Lecture Notes in Computer Science. Vol. 5038. Springer. pp. 319–333 . doi : 10.1007/978-3-540-68552-4_24 . ISBN 978-3-540-68548-7。

[32] サンダース、ピーター。シュルテス、ドミニク (2005)。ハイウェイ階層により、正確な最短パスのクエリが迅速化されます。アルゴリズム – ESA 2005。コンピュータサイエンスの講義ノート。 Vol. 3669.スプリンガー。 pp. 568–579 .土井: 10.1007/11561071_51。ISBN 978-3-540-29118-3。

[33] ハウプラー、ベルンハルト。フラディク、リチャード。ロジョニ、ヴァーツラフ。ロバート・タージャン。テクテク、ヤクブ（2024年10月28日）。「最悪ケースを超えたヒープによるダイクストラの普遍的最適性」。arXiv : 2311.11793 [ cs.DS ]。

[34] Brubaker, Ben (2024年10月25日). 「コンピュータ科学者がグラフを走査する最良の方法を確立」 . Quanta Magazine . 2024年12月9日取得.

[FOOTNOTEDial1969-35] 1969 にダイヤルしてください。

[FOOTNOTEAhujaMehlhornOrlinTarjan1990-36] 1 2 Ahuja et al. 1990 .

[FOOTNOTEThorup2000-37] ソーラップ 2000。

[FOOTNOTERaman1997-38] ラマン 1997。

[sniedovich_062-39] Sniedovich, M. (2006). "Dijkstraのアルゴリズムの再検討：動的計画法との関連" (PDF) . Journal of Control and Cybernetics . 35 (3): 599– 620.インタラクティブな計算モジュールを備えた論文のオンライン版。

[denardo_032-40] Denardo, EV (2003).動的計画法：モデルと応用. ミネオラ、ニューヨーク：ドーバー出版. ISBN 978-0-486-42810-9。

[sniedovich_102-41] スニエドヴィッチ、M. (2010).動的計画法：基礎と原理.フランシス＆テイラー. ISBN 978-0-8247-4099-3。

[FOOTNOTEDijkstra1959270-42] ダイクストラ 1959、p. 270。

[

[

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[

[

[ 21 ]

[ 22 ]

[ 2 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

ダイクストラ法

歴史

アルゴリズム

説明

擬似コード

優先度キューを使用する

証拠

基本ケース

誘導

実行時間

実用的な最適化と無限グラフ

双方向ダイクストラ

実用性能に関する考慮事項

距離による比較ソートの最適性

特殊派生型

関連する問題とアルゴリズム

動的計画法の観点から

関連項目

注記

参考文献

外部リンク

関連するトピック

最短

見つける

ため

アルゴリズム