जावास्क्रिप्ट में दिज्क्स्ट्रा का एल्गोरिथ्म

दिज्क्स्ट्रा का एल्गोरिथ्म एक भारित ग्राफ में नोड्स के बीच सबसे छोटा पथ खोजने के लिए एक एल्गोरिथ्म है। हम ग्राफ़ बनाते समय किनारों पर वज़न जोड़ने के लिए नए ऐडएडज और एडडायरेक्टेडएडज विधियों का उपयोग करेंगे। आइए देखें कि यह एल्गोरिथम कैसे काम करता है -

• दूरी संग्रह बनाएं और स्रोत नोड को छोड़कर सभी कोने की दूरियों को अनंत के रूप में सेट करें।
• स्रोत नोड को न्यूनतम-प्राथमिकता वाली कतार में प्राथमिकता 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 }