자바스크립트의 다익스트라 알고리즘

Dijkstra 알고리즘은 가중치 그래프에서 노드 간의 최단 경로를 찾는 알고리즘입니다. 새로운 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 }