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

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

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

入出力

• 入力: グラフ G=(V,E) 、 どこ $V$V は頂點(diǎn)の集合であり、 $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{?}v\mathrm{\ne }s$$dist(s)=0,dist(v)=∞?v=s

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

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

リラクゼーション - 數(shù)學(xué)的説明

• 初期化: 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) 、 アップデート：
  dist(v)=dist(u) w(u,v),前(v)=u

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

優(yōu)先キュー - 數(shù)學(xué)的説明

• キュー操作:

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

正しさの証明

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

強(qiáng)力な誘導(dǎo)とは何ですか?

強(qiáng)い帰納法は數(shù)學(xué)的帰納法の変形であり、ステートメントを証明するために、 $(P(n))$(P(n)) 、私たちは次の真実を仮定します (P(1),P(2),…,P(k)) 証明する $(P(k1))$( P(k 1)) 。これは、次のことだけを前提とする通常の誘導(dǎo)とは異なります。 $(P(k))$(P(k)) 証明する $(P(k1))$( P(k 1)) 。私の他の投稿で詳しく調(diào)べてください。

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

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

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

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

も正しいです。

JavaScriptの実裝

前提條件 (優(yōu)先キュー):

// 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;
  }
}

これは、優(yōu)先キューを使用したダイクストラのアルゴリズムの 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);

パスを再構(gòu)築

// 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;
  }
}

チュートリアルの例

グラフ表現(xiàn)

• ノード: A、B、C、D
• エッジ:
  • A→B=(1),A→C=(4)
  • 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→C,B→D.
     $$\text{距離}(C)=3,\text{dist}(D)=6$$dist(C)=3,dist(D)=6

4. プロセス C:

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

   • プロセス D:

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

   最終的な距離とパス

   dist(A)=0,dist(B)= 1、距離(C)=3、距離(D)=4
   
   
   A→B→C→D

   最適化と時(shí)間計(jì)算量

   ダイクストラのアルゴリズムの時(shí)間計(jì)算量をさまざまな優(yōu)先キュー実裝と比較:

   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. バイナリ ヒープ:
      • シンプルさと効率のバランスが取れているため、標(biāo)準(zhǔn)であり、一般的に使用されています。
   3. 二項(xiàng)ヒープ:
      • 理論上の保証はわずかに優(yōu)れていますが、実裝はより複雑です。
   4. フィボナッチ ヒープ:
      • ( O(1) ) 償卻減少キーを使用すると最高の理論的パフォーマンスが得られますが、実裝は困難です。
   5. ヒープのペアリング:
      • シンプルで、実際にはフィボナッチ ヒープに近いパフォーマンスを発揮します。

   結(jié)論

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

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

   ---

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

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

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

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

   ご意見や改善點(diǎn)をコメントでお?dú)葺Xに共有してください!