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

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

एक डिस्टेंस कलेक्शन बनाएं और सोर्स नोड को छोड़कर सभी वर्टेक्स की दूरियों को इनफिनिटी पर सेट करें।
सोर्स नोड को प्रायोरिटी 0 के साथ मिन-प्रायोरिटी क्यू में एनक्यू करें क्योंकि दूरी 0 है।
एक लूप शुरू करें जब तक प्रायोरिटी क्यू खाली न हो जाए और इससे न्यूनतम दूरी वाले नोड को डीक्यू करें।
पॉप्ड नोड से जुड़े नोड्स की दूरियों को अपडेट करें यदि "वर्तमान नोड दूरी + एज वजन < अगले नोड की दूरी", फिर नए डिस्टेंस के साथ नोड को क्यू में पुश करें।
प्रायोरिटी क्यू खाली होने तक जारी रखें।

यह एल्गोरिदम मूल रूप से मानता है कि सभी नोड्स सोर्स से अनंत दूरी पर हैं। फिर यह एजेज को ध्यान में रखना शुरू करता है और सोर्स से नोड्स की दूरियों को ट्रैक करता रहता है, अगर यह रास्ते में कम लागत वाला पाथ ढूंढता है तो उसे अपडेट करता है।

आइए कोड में इसके कार्यान्वयन को देखते हैं:

उदाहरण

djikstraAlgorithm(startNode) {
    let distances = {};
    // पिछले नोड्स का रेफरेंस स्टोर करता है
    let prev = {};
    let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
    // सभी नोड्स की दूरियों को स्टार्टनोड को छोड़कर इनफिनिटी पर सेट करें
    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 }