ダイクストラアルゴリズムを理解する: 理論から実装まで

ダイクストラのアルゴリズムは、グラフ理論でソース ノードからグラフ内の他のすべてのノードへの最短パスを見つけるために使用される古典的な経路探索アルゴリズムです。この記事では、アルゴリズムとその正しさの証明を検討し、JavaScript での実装を提供します。

ダイクストラのアルゴリズムとは何ですか?

ダイクストラのアルゴリズムは、非負のエッジ重みを持つ重み付きグラフ内の単一のソース ノードからの最短パスを見つけるように設計された貪欲なアルゴリズムです。これは 1956 年に Edsger W. Dijkstra によって提案され、現在でもコンピューター サイエンスで最も広く使用されているアルゴリズムの 1 つです。

入出力

• 入力: グラフ $G=(V、E)$G=(V,E) 、 どこ $V$V は頂点の集合であり、 $E$E はエッジのセットとソースノードです $s\in V$s∈V .
• 出力: からの最短パス距離 $s$s の他のすべてのノードに $V$V .

中心となる概念

1. 緩和: ノードまでの既知の最短距離を更新するプロセス。
2. Priority Queue: 暫定距離が最小のノードを効率的にフェッチします。
3. 貪欲なアプローチ: 距離が短い順にノードを処理します。

アルゴリズム

1. 距離の初期化:
   

   $$\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }s$$dist(s)=0,dist(v)=∞∀v=s

2. 優先キューを使用して、距離に基づいてノードを保存します。

3. 距離が最小のノードを繰り返し抽出し、その近傍を緩和します。

リラクゼーション - 数学的説明

• 初期化: $\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\text{すべて}v\mathrm{\ne }s$dist(s)=0,dist(v)=∞のためにllv=s

どこ $(s)$(s) はソースノードであり、 $(v)$(v) 他のノードを表します。

• リラックスステップ: 各エッジごと $(u,v)$(u,v) 重さで $w(u,v)$w(u,v) : もし $\text{dist}(v)>\text{dist}(u)w(u,v)$dist(v)>dist (う) w(u,v) 、 アップデート：
  $$\text{dist}(v)=\text{dist}(u)w(u,v),\text{prev}(v)=u$$dist(v)=dist(u) w(u,v),前(v)=u

機能する理由: 緩和により、より短いパスが見つかった場合に距離を段階的に更新することで、ノードへの最短パスが常に見つかるようになります。

優先キュー - 数学的説明

• キュー操作:

  • 優先キューは常にノードをデキューします $(u)$(u) 最小の暫定距離:
    $$u=\mathrm{a\; rg}\underset{v\in Q}{分}\text{dist}(v)$$u=arg v∈Q 分距離(v)
  • なぜ機能するのか: 最小のノードを処理することによって $(\text{dist}(v))$(dist(v)) 、ソースからへの最短パスを保証します。 $(u)$(u) .

正しさの証明

強帰納法を使用してダイクストラのアルゴリズムの正しさを証明します。

強力な誘導とは何ですか?

強い帰納法は数学的帰納法の変形であり、ステートメントを証明するために、 $(P(n))$(P(n)) 、私たちは次の真実を仮定します $(P(1),P(2)、\dots 、P(k))$(P(1),P(2),…,P(k)) 証明する $(P(k1))$( P(k 1)) 。これは、次のことだけを前提とする通常の誘導とは異なります。 $(P(k))$(P(k)) 証明する $(P(k1))$( P(k 1)) 。私の他の投稿で詳しく調べてください。

ダイクストラのアルゴリズムの正しさ (帰納的証明)

1. 基本ケース:
   
   ソースノード $(s)$(s) で初期化されます $\text{dist}(s)=0$距離(s)=0 正解です。

2. 帰納仮説:
   
   これまでに処理されたすべてのノードには正しい最短パス距離があると仮定します。

3. 帰納的ステップ:
   
   次のノード $(u)$(u) 優先キューからデキューされます。以来 $\text{dist}(u)$距離(u) は残りの最小距離であり、以前のノードはすべて正しい距離を持っています。 $\text{dist}(u)$距離(u)

も正しいです。

JavaScriptの実装

前提条件 (優先キュー):

// Simplified Queue using Sorting
// Use Binary Heap (good)
// or  Binomial Heap (better) or Pairing Heap (best) 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(node, priority) {
    this.queue.push({ node, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

これは、優先キューを使用したダイクストラのアルゴリズムの JavaScript 実装です。

function dijkstra(graph, start) {
  const distances = {}; // hold the shortest distance from the start node to all other nodes
  const previous = {}; // Stores the previous node for each node in the shortest path (used to reconstruct the path later).
  const pq = new PriorityQueue(); // Used to efficiently retrieve the node with the smallest tentative distance.

  // Initialize distances and previous
  for (let node in graph) {
    distances[node] = Infinity; // Start with infinite distances
    previous[node] = null; // No previous nodes at the start
  }
  distances[start] = 0; // Distance to the start node is 0

  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { node } = pq.dequeue(); // Get the node with the smallest tentative distance

    for (let neighbor in graph[node]) {
      const distance = graph[node][neighbor]; // The edge weight
      const newDist = distances[node] + distance;

      // Relaxation Step
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist; // Update the shortest distance to the neighbor
        previous[neighbor] = node; // Update the previous node
        pq.enqueue(neighbor, newDist); // Enqueue the neighbor with the updated distance
      }
    }
  }

  return { distances, previous };
}

// Example usage
const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 }
};

const result = dijkstra(graph, 'A'); // start node 'A'
console.log(result);

パスを再構築

// Simplified Queue using Sorting
// Use Binary Heap (good)
// or  Binomial Heap (better) or Pairing Heap (best) 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(node, priority) {
    this.queue.push({ node, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

チュートリアルの例

グラフ表現

• ノード: $A、B、C、D$A、B、C、D
• エッジ:
  • $A\to B=(1)、A\to C=(4)$A→B=(1),A→C=(4)
  • $B\to C=(2)、B\to D=(5)$B→C=(2),B→D=(5)
  • $C\to D=(1)$C→D=(1)

ステップバイステップの実行

1. 距離の初期化:
   

   $$\text{dist}(A)=0,\text{dist}(B)=\mathrm{\infty }、\text{dist}(C)=\mathrm{\infty }、\text{dist}(D)=\mathrm{\infty }$$dist(A)=0,dist(B)= ∞、距離(C)=∞、距離(D)=∞

2. プロセス A:

   • エッジをリラックス: $A\to B、A\to C\mathrm{.}$A→B,A→C.
     $$\text{距離}(B)=1,\text{dist}(C)=4$$dist(B)=1,dist(C)=4

3. プロセス B:

   • エッジをリラックス: $B\to C、B\to D\mathrm{.}$B→C,B→D.
     $$\text{距離}(C)=3,\text{dist}(D)=6$$dist(C)=3,dist(D)=6

4. プロセス C:

   • リラックスエッジ: $C\to D\mathrm{.}$C→D.
     $$\text{dist}(D)=4\mathrm{}テキスト\{距離\}(D)\; =\; 4$$dist(D)=4

   • プロセス D:

     • 今後の更新はありません。

   最終的な距離とパス

   $$\text{dist}(A)=0,\text{dist}(B)=1、\text{dist}(C)=3、\text{dist}(D)=4$$dist(A)=0,dist(B)= 1、距離(C)=3、距離(D)=4
   
   
   $$A\to B\to C\to D$$A→B→C→D

   最適化と時間計算量

   ダイクストラのアルゴリズムの時間計算量をさまざまな優先キュー実装と比較:

   Priority Queue Type	Insert (M)	Extract Min	Decrease Key	Overall Time Complexity
   Simple Array	O(1)	O(V)	O(V)	O(V^2)
   Binary Heap	O(log V)	O(log V)	O(log V)	O((V E) log V)
   Binomial Heap	O(log V)	O(log V)	O(log V)	O((V E) log V)
   Fibonacci Heap	O(1)	O(log V)	O(1)	O(V log V E)
   Pairing Heap	O(1)	O(log V)	O(log V)	O(V log V E) (practical)

   重要なポイント:

   1. 単純な配列:
      • extract-min の線形検索のため、大きなグラフでは非効率的です。
   2. バイナリ ヒープ:
      • シンプルさと効率のバランスが取れているため、標準であり、一般的に使用されています。
   3. 二項ヒープ:
      • 理論上の保証はわずかに優れていますが、実装はより複雑です。
   4. フィボナッチ ヒープ:
      • ( O(1) ) 償却減少キーを使用すると最高の理論的パフォーマンスが得られますが、実装は困難です。
   5. ヒープのペアリング:
      • シンプルで、実際にはフィボナッチ ヒープに近いパフォーマンスを発揮します。

   結論

   ダイクストラのアルゴリズムは、非負の重みを持つグラフ内の最短経路を見つけるための強力かつ効率的な方法です。制限はありますが (負のエッジの重みを処理できないなど)、ネットワーキング、ルーティング、その他のアプリケーションで広く使用されています。

   • リラクゼーションは、パスを繰り返し更新することで最短距離を保証します。
   • Priority Queue は、常に最も近いノードを処理し、正確さを維持することを保証します。
   • 正確さは帰納法によって証明されます。ノードの距離が確定すると、それが最短パスであることが保証されます。

   ---

   ここでは、厳密な証明と例とともにダイクストラのアルゴリズムを探索できる詳細なリソースをいくつか紹介します。

   • ダイクストラのアルゴリズム PDF
   • SlideShare の最短パス アルゴリズム

   さらに、ウィキペディアではこのトピックの優れた概要が提供されています。

   引用:
   [1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf

   ご意見や改善点をコメントでお気軽に共有してください!