जावास्क्रिप्ट में फ्लॉयड-वार्शल एल्गोरिदम

डिज्क्स्ट्रा का एल्गोरिदम एक नोड से अन्य सभी नोड्स तक के सबसे छोटे पाथ की दूरी/पाथ को खोजने के लिए उपयोग किया जाता है। ऐसे मामले होते हैं जहां हमें सभी नोड्स से अन्य सभी नोड्स तक के सबसे छोटे पाथ खोजने की आवश्यकता होती है। यहीं ऑल-पेयर्स शॉर्टेस्ट पाथ एल्गोरिदम काम आते हैं। सबसे अधिक उपयोग किया जाने वाला ऑल-पेयर्स शॉर्टेस्ट पाथ एल्गोरिदम फ्लॉयड-वार्शल एल्गोरिदम है।

फ्लॉयड-वार्शल एल्गोरिदम इस प्रकार काम करता है:

• हम दूरियों के N x N मैट्रिक्स को इनफिनिटी से इनिशियलाइज़ करते हैं।
• फिर प्रत्येक एज u, v के लिए, हम इस मैट्रिक्स को इस एज के वजन को दिखाने के लिए अपडेट करते हैं और एज v, v के लिए हम वजन को 0 पर अपडेट करते हैं।
• हम I, j और k इटरेटर्स के साथ 3 नेस्टेड लूप बनाते हैं। हर नोड I की हर नोड j से दूरी के लिए, हम k को इंटरमीडिएट पॉइंट्स के रूप में मानते हैं और दूरी को अपडेट करते हैं अगर हमें मौजूदा arr[i][j] से कम दूरी मिलती है।

मैट्रिक्स के बजाय, हम एक ऑब्जेक्ट का उपयोग करेंगे क्योंकि हमें इंडेक्स ट्रैक करने की आवश्यकता नहीं है अगर हम प्रत्येक नोड को दर्शाने के लिए जटिल ऑब्जेक्ट्स का उपयोग कर रहे हैं।

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

उदाहरण

floydWarshallAlgorithm() {
    let dist = {};
    for (let i = 0; i < this.nodes.length; i++) {
        dist[this.nodes[i]] = {};
        // मौजूदा एज के लिए डिस्ट को वजन के समान असाइन करें
        this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
        this.nodes.forEach(n => {
            // अन्य सभी नोड्स के लिए इसे इनफिनिटी असाइन करें
            if (dist[this.nodes[i]][n] == undefined)
                dist[this.nodes[i]][n] = Infinity;
            // सेल्फ एज के लिए डिस्ट को 0 असाइन करें
            if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
        });
    }
    this.nodes.forEach(i => {
        this.nodes.forEach(j => {
            this.nodes.forEach(k => {
                // जांचें कि i से k फिर k से j जाना बेहतर है
                // सीधे i से j जाने से। अगर हां तो अपडेट करें
                // i से j वैल्यू को नई वैल्यू से
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            });
        });
    });
    return dist;
}

आप इसका परीक्षण इस तरह कर सकते हैं:

उदाहरण

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);
console.log(g.floydWarshallAlgorithm());

आउटपुट

इससे निम्न आउटपुट मिलेगा:

{
    A: { C: 7, B: 3, D: 4, A: 0 },
    B: { A: 3, B: 0, C: 10, D: 7 },
    C: { A: 7, D: 3, B: 10, C: 0 },
    D: { A: 4, C: 3, B: 7, D: 0 }
}