ダイクストラのアルゴリズムの詳細な説明

この記事では、まず単一ソース最短経路問題から始め、次にベルマン・フォードアルゴリズムについて説明し、最後にダイクストラアルゴリズムについて具体的に説明します。ダイクストラアルゴリズムの各ステップを詳細に説明および分析し、このダイクストラアルゴリズムを徹底的に理解できるようにします。

1. 単一ソース最短経路問題

単一ソースの最短経路問題とは、グラフ G=(V, E) が与えられたときに、固定ソース頂点 s<-V から各 v<-V までの最短経路を見つけることが求められる問題です。簡単に言えば、グラフ G 内の固定点 s を見つけ、次に s を開始点として使用して、s からグラフ G 内の残りの点までの最短距離または経路を見つけることです。

この単一ソースの最短経路問題には、次のバリエーションがあります。

I. 単一目的地最短経路問題: 各頂点 v から指定された目的地 t までの最短経路問題。つまり、単一ソース最短経路問題の相対的な問題です。

II. 単一の頂点ペアの最短経路問題: 頂点 u と v が与えられた場合、u から v への最短経路を見つけます。

III. 各頂点間の最短経路問題:

任意の 2 つの頂点 u と v について、u から v への最短経路を見つけます。最も単純なアイデアは、各頂点をソースポイントとして扱い、単一ソースアルゴリズムを 1 回実行することでこの問題を解決することです。もちろん、もっと良い方法があります。

2. ベルマンフォードアルゴリズム

1. 回路の問題

最短パスには、負の重み付けされたループまたは正の重み付けされたループを含めることはできません。ダイクストラのアルゴリズムなどの一部の最短経路アルゴリズムでは、グラフ内のすべてのエッジの重みが非負である必要があります。たとえば、道路地図では、固定点 s から目的の頂点 v までの最短経路を見つける問題が解決されます。

2. ベルマンフォードアルゴリズム

Bellman-Ford アルゴリズムでは、ソースポイントから到達可能な負の重みのループがない限り、入力グラフに負の重みのエッジが存在することが許可されます。簡単に言えば、グラフには負の重みのエッジが存在する可能性がありますが、これらの負の重みのエッジは負の重みのループを構成せず、ループの形成に影響を与えません。さらに、ベルマンフォードアルゴリズム自体は、グラフ内のソースポイントから到達可能な負の重みループがあるかどうかを判断できます。負の重みループがある場合、アルゴリズムは FALSE を返し、ない場合は TRUE を返します。

ベルマンフォードアルゴリズムの詳細な説明

ベルマンフォード(G、w、s)

 INITIALIZE-SINGLE-SOURCE(G, s) // 各頂点を初期化する、O(V)  
 i ← 1 から |V[G]| - 1 まで
  する 各辺(u, v)∈E[G]について
RELAX(u, v, w) を実行します//各頂点 (V-1) に対して、緩和手法 O(E) を適用します (O((v-1)*E)) としてカウントされます)  
各辺(u, v)∈E[G]について
する  d[v] > d[u] + w(u, v) の場合
then return FALSE // グラフ内の各エッジをチェックして、負の重みループが含まれているかどうかを確認します。  
                                     //d[v]>d[u]+w(u,v)の場合は包含を意味し、FALSEを返します。  
 TRUEを返す// 負の重みループが含まれていない場合は TRUE を返す

上記から、ベルマンフォードアルゴリズムの時間計算量は O(V*E) であることがわかります。

3. グラフに負の重みループが含まれているかどうかという質問に関して:

定理によれば、uはvの親であると仮定する。すると、G(V,E)が有向グラフまたは無向グラフ（負の重みループを含まない）の場合、s<-V、sはGの任意の頂点であり、任意の辺（u、v）<-Vに対して、

d[s,v] <= d[s,u]+1 である。

この定理の詳細な証明については、『アルゴリズム入門』の第 22 章の補題 22.1 の証明を参照してください。あるいは、第 24 章の三角不等式を使用したベルマン-フォードアルゴリズムの正しさの証明に基づいて、上記の定理のバリエーションを導き出すこともできます。

つまり、グラフGに負の重みループが含まれていないと仮定すると、次のことが証明できる。

 d[v]=$(s，u)
      <=$(s,u)+w(u,v) //三角不等式によれば 
      =d[u]+w[u，v]

したがって、負の重みサイクルを含まないグラフでは、d[v]<=d[u]+w(u,v) と結論付けることができます。

したがって、上記のベルマンフォードアルゴリズムでは、d[v] > d[u]+w(u,v)の場合、=> 負の重みループが含まれ、FASLEが返されることは理解しにくいことではありません。

そうでない場合、=> に負の重みループが含まれていない場合は、TRUE を返します。

さて、ダイクストラアルゴリズムに移りましょう。

3. ダイクストラアルゴリズムをわかりやすく説明し、徹底的に分析する

I. リラクゼーションテクニックの紹介 RELAX

ダイクストラアルゴリズムは緩和技術を使用します。各頂点 v<-V に対して、ソースポイント s から v までの最短パスの重みの上限を記述する属性 d[v] が設定されます。
これを最短経路推定と呼びます。

まず、最短経路を推定し、先行ノードを初期化するのに O(V) の時間がかかります。

単一ソースの初期化(G, s) 
 各頂点v∈V[G]について
   d[v] ← ∞ を実行する
   π[v] ← NIL //O（V）  
 d[s] 0 
 
リラックス(u, v, w)
 d[v] > d[u] + w(u, v) の場合
 するとd[v] ← d[u] + w(u, v)となる。
  π[v] ← u //O(E) グラフ。

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

このダイクストラアルゴリズムには、INSERT (行 3)、EXTRACT-MIN (行 5)、および DECREASE-KEY (行 8 の RELAX、この減分キー操作を呼び出す) の 3 つのステップがあります。

ダイクストラ(G, w, s)
 INITIALIZE-SINGLE-SOURCE(G, s) // 各頂点を初期化する、O(V)  
 S ← Ø
 Q ← V[G] //挿入、O(1)  
  Q ≠ Øであるが
    do u ← EXTRACT-MIN(Q) // 単純 O(V*V); バイナリ/アイテム ヒープと FIB-HEAP はどちらも O(V*lgV) です。  
 S ← S ∪{u} 
     各頂点v ∈ Adj[u]について
           do RELAX(u, v, w) //単純な方法: O(E)、バイナリ/アイテムヒープ、E*O(lgV)、FIB-HEAP、E*O(1)。

4. ダイクストラアルゴリズムの実行時間

先に進む前に、問題を述べなければなりません。DIJKSTRA (G, w, s) アルゴリズムの 5 行目、EXTRACT-MIN (Q) は、最小優先度キューの具体的な実装です。ダイクストラアルゴリズムの実行時間は、この最小優先度キューの特定の実装によって異なります。

最小優先度キューの 3 つの実装方法:

1. 1 から |V| まで番号が付けられた頂点を使用して、各 d[v] を、上記の DIJKSTRA(G, w, s) に示すように、配列内の対応する v 番目の項目に格納します。ダイクストラのアルゴリズムの実行時間は O(V^2+E) です。

2. 最小優先度キューがバイナリ/アイテムヒープによって実装されている場合、EXTRACT-MIN(Q) の実行時間は O(V*lgV) なので、ダイクストラのアルゴリズムの実行時間は O(V*lgV+E*lgV) です。すべての頂点がソースポイントから到達可能な場合、O((V+E)*lgV)=O(E*lgV) です。疎グラフの場合、E=O(V^2/lgV)となり、このダイクストラアルゴリズムの実行時間はO(V^2)となります。

3. フィボナッチヒープを使用して最小優先度キューを実装する場合、EXTRACT-MIN(Q) の実行時間は O(V*lgV) なので、このダイクストラアルゴリズムの実行時間は O(V*lgV+E) になります。

要約すると、この最小優先度キューの 3 つの実装方法は次のように比較されます。

|V|<<|E|の場合、DIJKSTRA(G, w, s) + FIB-HEAP-EXTRACT-MIN(Q)、つまりフィボナッチヒープを使用して最小優先度キューを実装します。
メリットが反映されます。

5. ダイクストラアルゴリズム + FIB-HEAP-EXTRACT-MIN(H)、最小優先度キューを実装するためのフィボナッチヒープ

上記から、フィボナッチヒープを使用して最小優先度キューを実装すると、実行時間が O (VlgV + E) に改善されることがすでにわかっています。 |V| EXTRACT-MIN操作（それぞれ償却コストO(lgV)）、および|E| DECREASE-KEY操作（それぞれ償却時間O(1)）。

次に、DIJKSTRA(G, w, s) におけるフィボナッチヒープを用いた最小優先度キューの実装操作に焦点を当てます。

上記から、DIJKSTRA アルゴリズムには次の 3 つのステップが含まれていることがすでにわかっています。

INSERT (行 3)、EXTRACT-MIN (行 5)、および DECREASE-KEY (行 8 の RELAX)。

まず、ダイクストラアルゴリズム + FIB-HEAP-EXTRACT-MIN(H) のアルゴリズムを直接示します。

ダイクストラ(G, w, s)
 単一ソースの初期化(G, s)
 S ← Ø
 Q ← V[G] // 行3、INSERT操作、O(1)  
  Q ≠ Øであるが
    do u ← EXTRACT-MIN(Q) //行5、EXTRACT-MIN演算、V*lgV  
       S ← S ∪{u} 
       各頂点v ∈ Adj[u]について
           do RELAX(u, v, w) // 8行目、RELAX操作、E*O(1)  
 
 FIB-HEAP-EXTRACT-MIN(H) //償却コストはO(lgV)  
  z ← 最小[H] 
   z ≠ NILの場合
     次に、 zの子xごとに
               Hのルートリストにxを追加する
                 p[x] ← ゼロ
          Hのルートリストからzを削除する
           z = 右[z]の場合
             min[H] ← NIL 
            そうでない場合はmin[H] ← right[z]
                 統合(H)
         n[H] ← n[H] - 1
 zを返す

6. ダイクストラ法+フィボナッチヒープの各ステップの詳細な分析

さて、次に、上記の操作を段階的に詳しく説明します。

行3のINSERT操作:

 FIB-HEAP-INSERT(H, x) //償却コスト、O(1)。  
  度[x] ← 0
  p[x] ← ゼロ
  子[x] ← NIL
  左[x] ← x
  右[x] ← x
  マーク[x] ← FALSE
  xを含むルートリストをルートリストHと連結する
   min[H] = NIL または key[x] < key[min[H]]の場合
     すると min[H] ← x
 n[H] ← n[H] + 1

5行目のEXTRACT-MIN演算:

 FIB-HEAP-EXTRACT-MIN(H) //償却コストはO(lgV)  
  z ← 最小[H] 
   z ≠ NILの場合
    次に、 zの子xごとに
              Hのルートリストにxを追加する
                p[x] ← ゼロ
        Hのルートリストからzを削除する
         z = 右[z]の場合
           min[H] ← NIL 
          そうでない場合はmin[H] ← right[z]
              CONSOLIDATE(H) //CONSOLIDATEアルゴリズムは以下の通りです。  
        n[H] ← n[H] - 1
 zを返す

次の図は、FIB-HEAP-EXTRACT-MIN プロセスの概略図です。

統合(H) 
  i ← 0 から D(n[H]) まで
       A[i] ← NILを実行する
  Hのルートリストの各ノードwについて
       x ← wを実行する
         d ← degree[x] // 子の数 
          A[d] ≠ NILであるが
             する← A[d] 
                キー[x] > キー[y]の場合
                 x <-> yを交換する
              FIB-HEAP-LINK(H, y, x) // 以下に示す。  
             A[d] ← ゼロ
             d ← d + 1
        A[d] ← x
 min[H] ← ゼロ
  i ← 0 から D(n[H]) まで
    する  A[i] ≠ NILの場合
         次にA[i]をHのルートリストに追加する
               min[H] = NIL または key[A[i]] < key[min[H]] の場合
              すると min[H] ← A[i] 
 
 FIB-HEAP-LINK(H, y, x) //yはxにリンクされています。  
 Hのルートリストからyを削除する
yをxの子にして、degree[x]を増分する
 マーク[y] ← FALSE

8行目のRELAXの操作は上記に示されています。

リラックス(u, v, w) 
  d[v] > d[u] + w(u, v) の場合
   するとd[v] ← d[u] + w(u, v)となる。
      π[v] ← u //O（E）

一般的に、ダイクストラのアルゴリズムでは、DECREASE-KEY は EXTRACT-MIN よりもはるかに頻繁に呼び出されます。
したがって、EXTRACT-MIN 操作の償却時間を増やすことなく、DECREASE-KEY 操作の償却時間を最小限に抑えることで、バイナリヒープよりも高速な実装を実現できます。

以下は、バイナリヒープ、二項式ヒープ、フィボナッチヒープのさまざまな操作の時間計算量の比較です。

操作バイナリヒープ（最悪の場合）二項式ヒープ（最悪の場合）フィボナッチヒープ（償却）

ヒープを作る Θ(1) Θ(1) Θ(1)
Θ(lg n) O(lg n) Θ(1) を挿入する
最小Θ(1) O(lg n) Θ(1)
抽出最小Θ(lg n) Θ(lg n) O(lg n)
和集合Θ(n) O(lg n) Θ(1)
減少キー Θ(lg n) Θ(lg n) Θ(1)
削除 Θ(lg n) Θ(lg n) O(lg n)

フィボナッチヒープについては、今後このブログでさらに詳しく調査し、詳しく説明する予定です。同時に、この記事は今後も深化と拡張を続けていきます。

オリジナルリンク: http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx

【編集者のおすすめ】