อัลกอริทึมของ Dijkstra ใน Javascript

อัลกอริทึมของ 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 }