ダイクストラアルゴリズムに関する予備的研究

ダイクストラアルゴリズム (Dijkstra アルゴリズムとも呼ばれます) は、有向グラフ内の単一のソース ポイントから他の頂点までの最短経路問題を解決します。

たとえば、グラフの頂点が都市を表し、辺の重みが都市間の運転距離を表す場合、ダイクストラのアルゴリズムを使用して 2 つの都市間の最短経路を見つけることができます。

1. ダイクストラ法の実装

ダイクストラのアルゴリズムの入力は、重み付き有向グラフ G と G 内のソース頂点 S で構成されます。

G 内のすべての頂点の集合を V で表し、G 内のすべての辺の集合を E で表します。 (u, v)は頂点uからvへのパスがあり、辺の重みは重み関数w: E → [0, ∞]によって定義されることを示します。

したがって、w(u, v) は頂点 u から頂点 v までの非負のコストです。エッジのコストは、2 つの頂点間の距離として考えることができます。任意の 2 点間のパスのコストは、そのパス上のすべてのエッジのコストの合計です。

V に頂点 s と t がある場合、ダイクストラのアルゴリズムは s から t への最小コスト パス (つまり、最短パス) を見つけることができます。このアルゴリズムは、グラフ内の頂点 s から他の任意の頂点までの最短経路を見つけるためにも使用できます。

さて、このアルゴリズムの具体的な実装を見てみましょう。

ダイクストラのアルゴリズム 1 の実装(Wikipedia):

u := Extract_Min(Q)は、頂点集合Q内でd[u]値が最小の頂点uを検索します。この頂点はセット Q から削除され、ユーザーに返されます。

関数 Dijkstra(G, w, s)
 V[G]内の各頂点vについて// 初期化 
          d[v] := 無限大
          前[v] := 未定義
    d[s] := 0
    S := 空集合
   Q := すべての頂点の集合
     Q が空集合ではない場合// ダイクストラアルゴリズム本体 
          u := 抽出最小値(Q)
          S := Sユニオン{u} 
         uから出ている各辺(u,v)について
              if d[v] > d[u] + w(u,v) // エッジ(u,v)を展開 
                      d[v] := d[u] + w(u,v)
                       前[v] := u

s と t の間の最短経路のみを探している場合は、9 行目に条件を追加して、u = t の場合にプログラムを終了できます。これで、s から t への最短経路を反復して見つけることができます。

 s := 空のシーケンス
u := t
定義されるu
   Sの先頭にuを挿入する
   u := 前[u]

ここで、シーケンス S は、s から t への最短経路の頂点の集合です。

ダイクストラのアルゴリズム 2 の実装(アルゴリズムの紹介):

ダイクストラ(G, w, s)
 単一ソースの初期化(G, s)
 S ← Ø
 Q ← V[G] //V*O（1）  
 Q ≠ Øであるが
    u ← EXTRACT-MIN(Q) //EXTRACT-MIN、V*O (V)、V*O (lgV) を実行します。  
    S ← S ∪{u} 
  各頂点v ∈ Adj[u]について
   do RELAX(u, v, w) //緩和法、E*O(1)、E*O(lgV)。  

ダイクストラのアルゴリズムは、集合 S に挿入する頂点として常に VS 内の「最も軽い」または「最も近い」頂点を選択するため、貪欲な戦略を使用していると言えます。

このダイクストラアルゴリズムの初期時間計算量はO(V*V+E)です。ソースポイントが到達可能な場合、O(V*lgV+E*lgV)=>O(E*lgV)
疎グラフの場合、E=V*V/lgVとなり、アルゴリズムの時間計算量はO(V^2)になります。

しかし、フィボナッチ ヒープが優先キューを実装する場合、アルゴリズムの時間計算量は O (V*lgV + E) になることがわかっています。

2. ダイクストラアルゴリズムの実行速度

ビッグオー表記法を使用して、ダイクストラのアルゴリズムの実行時間を、辺の数 m と頂点の数 n の関数として表すことができます。ダイクストラのアルゴリズムの最も単純な実装は、リンク リストまたは配列を使用してすべての頂点の集合 Q を格納することです。これにより、Q 内の最小の要素を検索する操作 (Extract-Min(Q)) では、Q 内のすべての要素の線形検索のみが必要になります。
この場合、アルゴリズムの実行時間は O(E^2) です。

E^2 未満のエッジを持つスパース グラフの場合、隣接リストを使用して Dijkstra アルゴリズムをより効率的に実装できます。同時に、最小の頂点 (Extract-Min) を見つけるための優先キューとして、バイナリ ヒープまたはフィボナッチ ヒープが必要になります。

バイナリ ヒープを使用する場合、アルゴリズムには O((V+E)logE) かかります。フィボナッチ ヒープを使用するとパフォーマンスがわずかに向上し、アルゴリズムの実行時間が O(V+ElogE) になります。

Open Shortest Path First (OSPF) アルゴリズムは、ネットワーク ルーティングにおける Dijkstra アルゴリズムの特定の実装です。ダイクストラのアルゴリズムとは異なり、ベルマン・フォード アルゴリズムは、グラフ内に負の総コストを持ち、ソース ポイント s から到達可能なサイクルがない限り、負の重み付きエッジを持つグラフに使用できます (そのようなサイクルがある場合、サイクルに沿って複数回ループすると総コストが無制限に削減されるため、最短パスは存在しません)。

最短経路問題に関連する最も有名な問題の 1 つは巡回セールスマン問題です。これは、すべてのポイントを正確に 1 回通過し、最終的に出発点に戻る最短経路を見つけることを要求する問題です。

しかし、この問題は NP 完全です。つまり、最短経路問題とは異なり、巡回セールスマン問題には多項式時間解が存在する可能性は低いということです。ある点から目標点までの距離を推定するために使用できる既知の情報がある場合は、代わりに A* 検索アルゴリズムを使用して、最短経路の検索範囲を縮小できます。

BFS、DFS、Kruskal、Prim、Dijkstra アルゴリズムの時間計算量の比較:

一般的に言えば、BFS アルゴリズムと DFS アルゴリズムの時間計算量は O (V + E) であり、最小全域木アルゴリズムであるクラスカル アルゴリズムとプリム アルゴリズムの時間計算量は O (E * lgV) であることがわかっています。 Prim のアルゴリズムがフィボナッチ ヒープを使用して実装されている場合、アルゴリズムの時間計算量は O(E+V*lgV) です。|V|<<|E| の場合、E+V*lgV は大幅な改善となります。 //|V|<<|E|、=> O(E+V*lgV) << O(E*lgV)、正解です。

ダイクストラ アルゴリズムでは、フィボナッチ ヒープが優先キューとして使用される場合、アルゴリズムの時間計算量は O (V*lgV + E) です。 // ご覧のとおり、アルゴリズムの時間計算量は、フィボナッチ ヒープを使用して Prim アルゴリズムを実装した場合と同じです。

したがって、BFS、Prime、および Dijkstra アルゴリズムには類似点があり、各アルゴリズムの時間計算量を比較するだけでそれらを垣間見ることができると言えます。

3. グラフィカル分析のためのダイクストラアルゴリズム

上記のやや複雑な情報を読んだ後でも、このアルゴリズムを完全に理解しているわけではありません。関係ないから、写真を撮ってみましょう。このアルゴリズムの概念をもう一度説明させてください。

ダイクストラ アルゴリズムは、1 つのノードから他のすべてのノードまでの最短経路を計算するために使用される典型的な最短経路アルゴリズムです。
ただし、これは非負の重みエッジを対象とします。

開始点を中心に層ごとに外側に広がり、終了点に到達するのが最大の特徴です。
[ダイクストラアルゴリズムは最短経路の最適解を得ることができますが、多くのノードを横断して計算するため、効率が低くなります。

次の図をご覧ください。

下の図に示すように、A をソース ポイントとし、A から他のすべての頂点 (B、C、D、E、F) までの最短経路を見つけます。隣接する線分間の距離、つまり重みが線上にマークされます。

（注：この図はランダムに描かれており、隣接する頂点間の距離は図の視覚的な長さと1対1にはなりません）

ダイクストラ無向グラフ

アルゴリズムの実行手順は次のとおりです。

ダイクストラのアルゴリズムをよく理解していますか?さて、この記事は終わりです。

オリジナルリンク: http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx

【編集者のおすすめ】

1. いくつかの最短経路アルゴリズムの比較
2. C/C++アルゴリズム設計における任意のビット幅の使用
3. 文字の組み合わせをソートするJavaアルゴリズム
4. Javaは一般的な組み合わせアルゴリズムを実装する
5. Android マーケットのランキングアルゴリズムとルールの分析