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

ダイクストラのアルゴリズムは、重み付きグラフ内のノード間の最短経路を見つけるためのアルゴリズムです。新しいaddEdgeメソッドとaddDirectedEdgeメソッドを使用して、グラフを作成するときにエッジに重みを追加します。このアルゴリズムがどのように機能するかを見てみましょう-

• 距離コレクションを作成し、ソースノードを除くすべての頂点の距離を無限大に設定します。
• 距離が0であるため、優先度0の最小優先度キューにソースノードをエンキューします。
• 優先キューが空になるまでループを開始し、ノードからの距離が最小になるようにノードをデキューします。
• 「現在のノードの距離+エッジの重み<次のノードの距離」の場合は、接続されているノードからポップされたノードまでの距離を更新してから、新しい距離のノードをキューにプッシュします。
• 優先キューが空になるまで続行します。

このアルゴリズムが基本的に行うことは、すべてのノードがソースから無限の距離にあることを前提としています。次に、エッジを考慮し始め、途中で低コストのパスが見つかった場合は、ソースからのノードの距離を追跡し、同じように更新します。

この実装をコードで見てみましょう-

例

djikstraAlgorithm(startNode) {
   let distances = {};

   // Stores the reference to previous nodes
   let prev = {};
   let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Set distances to all nodes to be infinite except startNode
   distances[startNode] = 0;
   pq.enqueue(startNode, 0);
   this.nodes.forEach(node => {
      if (node !== startNode) distances[node] = Infinity;
      prev[node] = null;
   });

   while (!pq.isEmpty()) {
      let minNode = pq.dequeue();
      let currNode = minNode.data;
      let weight = minNode.priority;
      this.edges[currNode].forEach(neighbor => {
         let alt = distances[currNode] + neighbor.weight;
         if (alt < distances[neighbor.node]) {
            distances[neighbor.node] = alt;
            prev[neighbor.node] = currNode;
            pq.enqueue(neighbor.node, distances[neighbor.node]);
         }
      });
   }
   return distances;
}

-

例

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);

console.log(g.djikstraAlgorithm("A"));

出力

これにより、出力が得られます-

{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }