ダイクストラのアルゴリズム

ダイクストラのアルゴリズム

aとb の間の最短経路を見つけるためのダイクストラのアルゴリズム。最小距離を持つ未訪問の頂点を選択し、そこから各未訪問の隣接頂点までの距離を計算し、小さい場合は隣接頂点の距離を更新します。隣接頂点の処理が完了したら、訪問済みとしてマークします (赤に設定)。
クラス	探索アルゴリズム 貪欲アルゴリズム 動的 計画法[1]
データ構造	グラフ 通常は優先キューやヒープと組み合わせて最適化に使用されます[2] [3]
最悪の場合の パフォーマンス	${\displaystyle \Theta (|E|+|V|\log |V|)}$[3]

ダイクストラのアルゴリズム（/ ˈ d aɪ k s t r ə z / DYKE -strəz）は、例えば道路網を表す重み付きグラフ内のノード間の最短経路を見つけるアルゴリズムである。これは1956年にコンピュータ科学者のエドガー・W・ダイクストラによって考案され、3年後に発表された。^{[4] [5] [6]}

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

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

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

多くの分野、特に人工知能においては、ダイクストラのアルゴリズムまたはその変種が均一コスト探索を提供し、より一般的なベストファースト探索の考え方の例として定式化されています。^[12]

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

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

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

このアルゴリズムには、開始ノードと、開始ノードとNの間の距離を持つノードN が必要です。ダイクストラのアルゴリズムは、無限の距離から開始し、段階的に距離を改善しようとします。

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

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

現在の交差点から、すべての隣接(直接接続) 交差点までの距離は、現在の交差点のラベル (値) と隣接交差点までの距離を合計して計算され、その合計と隣接交差点の既存のラベルの小さい方を使用して隣接交差点にラベルが付けられます。つまり、現在の交差点を通る隣接交差点までのパスが、以前に計算されたパスよりも短い場合、隣接交差点にラベルが付けられます。その場合、隣接交差点への道路に矢印を付けてマークし、他の矢印を消します。現在の交差点の各隣接交差点までの距離が計算された後、現在の交差点は訪問済みとしてマークされます。ラベルが最も小さい未訪問の交差点が現在の交差点になり、目的地のラベルよりも小さいラベルを持つすべてのノードが訪問されるまで、このプロセスが繰り返されます。

目的地のラベルよりも小さいラベルを持つ未訪問のノードがなくなると、残りの矢印は最短パスを示します。

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

1  関数Dijkstra(グラフ,ソース):
 2     Graph.Vertices内の各頂点vに対して
 3 つ      :
 4 距離[ v ] ← 無限大
 5 前へ[ v ] ← 未定義
 6 vをQに追加
 7 dist[ソース] ← 0
 8     
 9       Qが空ではない場合 :
10           u ←最小距離[u]を持つQの頂点
11 Qからuを削除します
12         
13          まだQ内にあるuの各隣接vについて:
14               alt ← dist[ u ] + Graph.Edges( u , v )
15               alt < dist[ v ]の場合 :
16 ディストリビューション[ v ] ←代替
17 前[ v ] ← u
18
19       dist[], prev[]を
返す

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

1   S ← 空のシーケンス
2   u ← target 
3   prev[ u ] が定義されているかu = sourceの場合:           // 頂点が到達可能な場合は続行
4       uが定義されている場合:                        // スタック S を使用して最短経路を構築
5 Sの先頭にu を挿入// 頂点をスタックにプッシュ
6           u ← prev[ u ]                            // target から source までトラバース          

ここで、シーケンスSは、ソースからターゲットへの最短パスの 1 つを構成する頂点のリストです。パスが存在しない場合は、空のシーケンスになります。

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

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

1   関数Dijkstra(グラフ,ソース):
2 頂点優先キューQを作成する
3
4 dist[ source ] ← 0                           // 初期化
5        Q .add_with_priority( source , 0)             // 関連付けられている優先度は dist[·] に等しい
6Graph.Vertices内の各頂点vに対して
7        :
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が空でないとき:                      // メインループ
15           u ← Q .extract_min()                    // uの各近傍vについて、最適な頂点
16          を削除して返します:              // u の近傍 v をすべて調べます
17               alt ← dist[ u ] + Graph.Edges( u , v )
18               alt < dist[ v ]の場合 :
19 prev[ v ] ← u 
20 dist[ v ] ← alt 
21                   Q .decrease_priority( v , alt )
22
23      戻り値、前

初期化フェーズで優先キューをすべてのノードで埋める代わりに、ソースのみを含むように初期化することができます。その場合、ブロック内で、decrese_priority()はadd_with_priority()操作になります。^{[7] : 198}if alt < dist[v]

さらに別の方法としては、優先キューに無条件にノードを追加し、代わりに抽出（）後に再訪問していないか、ブロック内にまだ短い接続が見つかっていないかをチェックする方法があります。これは、関連する優先度をキューからさらに抽出し、ループ内でさらに処理するだけで実行できます。^[20]u ← Q.extract_min()if alt < dist[v]pif p == dist[u]while Q is not empty

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

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

不変仮説: 訪問した各ノードvについて、はソースからvへの最短距離であり、訪問していない各ノードuについて、は訪問したノードのみを経由して移動する場合のソースからuへの最短距離、またはそのようなパスが存在しない場合は無限大です。(注: は訪問していないノードの実際の最短距離であるとは想定していませんが、は実際の最短距離です) dist[v]dist[u]dist[u]dist[v]

基本ケースは、訪問されたノードが 1 つだけであるsource の場合です。負の重みは許可されないため、その距離は 0 と定義され、これが最短距離となります。したがって、仮説は成立します。

仮説が訪問ノードに当てはまると仮定し、それがノードに当てはまることを示すために、u を次に訪問するノード、つまり が最小のノードとします。 はソースからuまでの最短距離である、という主張です。 ${\displaystyle k}$${\displaystyle k+1}$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]
• 後者の場合、w を最短経路上の最後から 2 番目のノードとします。つまり、 となります。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 を持つグラフ上のダイクストラ法の実行時間の上限は、big-O 記法 を用いて、辺の数 ( )と頂点の数 ( ) の関数として表すことができます。計算量上限は、集合Q を表すのに使用するデータ構造に主に依存します。以下では、 は任意の単純グラフに対して成り立つため上限を簡略化できますが、この簡略化では、問題によっては の別の上限が成り立つ可能性があるという事実が無視されています。 ${\displaystyle |E|}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle O(|V|^{2})}$${\displaystyle |E|}$

頂点集合Qの任意のデータ構造の実行時間は次のようになる: ^[2]

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

ここで、およびはそれぞれQにおける減少キー操作と最小値抽出操作の複雑度です。 ${\displaystyle T_{\mathrm {dk} }}$${\displaystyle T_{\mathrm {em} }}$

ダイクストラのアルゴリズムの最も単純なバージョンでは、頂点セットQ をリンクリストまたは配列として保存し、辺を隣接リストまたは行列として保存します。この場合、抽出最小値はQ内のすべての頂点を単純に線形検索するため、実行時間は です。 ${\displaystyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$

疎グラフ、つまり辺の数がはるかに少ないグラフの場合、ダイクストラのアルゴリズムは、グラフを隣接リストの形式で保存し、自己バランス型二分探索木、二分ヒープ、ペアリングヒープ、フィボナッチヒープ、または優先度ヒープを優先キューとして使用して、最小値の抽出を効率的に実装することで、より効率的に実装できます。二分ヒープでキー減少ステップを効率的に実行するには、各頂点をヒープ内の位置にマップする補助データ構造を使用し、優先度キューQが変化するとこの構造を更新する必要があります。自己バランス型二分探索木または二分ヒープでは、アルゴリズムには次のものが必要です。 ${\displaystyle |V|^{2}}$

${\displaystyle \Theta ((|E|+|V|)\log |V|)}$

最悪の場合、時間です。連結グラフの場合、この時間制限は に簡略化できます。フィボナッチヒープはこれを に改善します。 ${\displaystyle \Theta (|E|\log |V|)}$

${\displaystyle \Theta (|E|+|V|\log |V|).}$

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

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

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

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

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

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

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

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

弧の重みが小さな整数（パラメータ で制限される）の場合、速度を上げるために特殊なキューを使用できます。このタイプの最初のアルゴリズムは、正の整数の辺の重みを持つグラフに対するDial のアルゴリズム^[29]で、バケット キューを使用して実行時間 を取得します。優先キューとしてVan Emde Boas 木を使用すると、複雑さは になります。^{[30]新しい}基数ヒープとよく知られているフィボナッチ ヒープの組み合わせに基づく別の興味深いバリエーションは、時間 で実行されます。^[30]最後に、この特殊なケースで最高のアルゴリズムは^[31]時間と時間で実行されます。^[32]${\displaystyle C}$${\displaystyle O(|E|+|V|C)}$${\displaystyle O(|E|\log \log C)}$${\displaystyle O(|E|+|V|{\sqrt {\log C}})}$${\displaystyle O(|E|\log \log |V|)}$${\displaystyle O(|E|+|V|\min\{(\log |V|)^{1/3+\varepsilon },(\log C)^{1/4+\varepsilon }\})}$

ダイクストラのオリジナル アルゴリズムは、変更を加えて拡張できます。たとえば、数学的に最適ではないソリューションを提示することが望ましい場合があります。最適ではないソリューションのランク付けされたリストを取得するには、まず最適ソリューションを計算します。最適ソリューションに現れる単一のエッジをグラフから削除し、この新しいグラフの最適ソリューションを計算します。元のソリューションの各エッジを順に削除し、新しい最短経路を計算します。次に、2 番目のソリューションをランク付けして、最初の最適ソリューションの後に提示します。

ダイクストラのアルゴリズムは通常、リンクステート ルーティング プロトコルの動作原理です。最も一般的なのは OSPFとIS-ISです。

ダイクストラのアルゴリズムとは異なり、ベルマン・フォードのアルゴリズムは、グラフにソース頂点sから到達可能な負のサイクルが含まれていない限り、負のエッジ重みを持つグラフで使用できます。このようなサイクルが存在すると、サイクルをトラバースするたびにラベルが低くなるため、最短パスが見つからないことを意味します。(このステートメントは、「パス」が頂点を繰り返すことが許可されていることを前提としています。グラフ理論では、これは通常許可されません。理論計算機科学では、多くの場合許可されます。) ダイクストラのアルゴリズムをベルマン・フォードのアルゴリズム (負のエッジを削除し、負のサイクルを検出する) と組み合わせることで、負の重みを処理できるように適応させることができます。ジョンソンのアルゴリズム。

A * アルゴリズムは、ターゲットまでの距離の下限を提供する追加情報が利用可能な場合に、探索する必要があるサブグラフのサイズを縮小する Dijkstra アルゴリズムの一般化です。

ダイクストラのアルゴリズムの基礎となるプロセスは、プリムのアルゴリズムで使用される貪欲プロセスに似ています。プリムの目的は、グラフ内のすべてのノードを接続する最小全域木を見つけることです。ダイクストラは 2 つのノードのみを対象とします。プリムのアルゴリズムでは、開始ノードからのパスの合計重みは評価されず、個々のエッジのみが評価されます。

幅優先探索は、優先度キューがFIFOキューに退化する、重み付けされていないグラフ上の Dijkstra アルゴリズムの特殊なケースとして考えることができます。

高速マーチング法は、三角形メッシュ上の測地線距離を計算するダイクストラのアルゴリズムの連続バージョンとして考えることができます。

動的計画法の観点から見ると、ダイクストラ法は、最短経路問題の動的計画法関数方程式をリーチング法で解く逐次近似法である。^{[33] [34] [35]}

実際、ダイクストラはアルゴリズムの背後にあるロジックを次のように説明している。^[36]

問題 2.与えられた 2 つのノードPとQ間の全長が最小となる経路を見つけます。RがPからQへの最小経路上のノードである場合、 Q を知っているということはPからRへの最小経路を知っているということであるという事実を利用します。

これは、最短経路問題の文脈における ベルマンの 最適性原理の言い換えです。

• A*検索アルゴリズム
• ベルマン・フォードアルゴリズム
• ユークリッド最短経路
• フロイド・ワーシャルアルゴリズム
• ジョンソンのアルゴリズム
• 最長経路問題
• 並列全ペア最短経路アルゴリズム

• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。 「セクション 24.3: ダイクストラのアルゴリズム」。アルゴリズム入門(第 2 版)。MIT プレスとマグロウヒル。 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)。フィボナッチヒープと改良されたネットワーク最適化アルゴリズムにおけるその利用。第 25 回コンピュータサイエンスの基礎に関する年次シンポジウム。IEEE。pp . 338–346。doi : 10.1109 /SFCS.1984.715934。
• 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.
• Zhan, F. Benjamin; Noon, Charles E. (1998年2 月)。「最短経路アルゴリズム: 実際の道路ネットワークを使用した評価」。交通科学。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 日 - 通信システムのためのモデル技術の研究。オハイオ州クリーブランド: Case Institute of Technology。
• Knuth, DE (1977). 「ダイクストラアルゴリズムの一般化」.情報処理レター. 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.
• ラマン、ラジーブ (1997)。 「単一ソース最短経路問題に関する最近の結果」。SIGACTニュース。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 を使用したダイクストラ アルゴリズムの実装、Robert Cecil Martin、The Clean Code Blog