Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> JavaScript

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


ग्राफ थ्योरी में, शॉर्टेस्ट पाथ समस्या एक ग्राफ में दो वर्टेक्स (या नोड्स) के बीच एक पाथ खोजने की समस्या है जैसे कि इसके घटक एजेज के वजन का योग न्यूनतम हो। यहां हमें अपने add edge और add directed मेथड्स को संशोधित करने की आवश्यकता है ताकि एजेज को वजन जोड़ने की अनुमति मिल सके।

आइए देखते हैं कि हम इसे कैसे जोड़ सकते हैं:

उदाहरण

/**
 * दोनों दिशाओं में समान वजन के साथ 2 एज जोड़ता है
 *
 *  वजन
 * node1 <================> node2
 *  वजन
 * */
addEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight: weight });
    this.edges[node2].push({ node: node1, weight: weight });
}
/**
 * निम्नलिखित एज जोड़ें:
 *
 *  वजन
 * node1 ----------------> node2
 * */
addDirectedEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight: weight });
}
display() {
    let graph = "";
    this.nodes.forEach(node => {
        graph += node + "->" + this.edges[node].map(n => n.node).join(", ")+ "\n";
    });
    console.log(graph);
}

अब जब हम अपने ग्राफ में एज जोड़ते हैं, अगर हम वजन निर्दिष्ट नहीं करते हैं, तो उस एज को डिफ़ॉल्ट वजन 1 असाइन किया जाता है। अब हम इसका उपयोग शॉर्टेस्ट पाथ एल्गोरिदम लागू करने के लिए कर सकते हैं।


  1. ठीक k किनारों के साथ सबसे छोटा पथ ठीक k किनारों के साथ सबसे छोटा पथ

    एक निर्देशित ग्राफ प्रत्येक शीर्ष जोड़े के बीच भार के साथ प्रदान किया जाता है, और दो शीर्ष u और v भी प्रदान किए जाते हैं। हमारा कार्य शीर्ष u से शीर्ष v तक की सबसे छोटी दूरी ढूंढना है, ठीक k संख्या के किनारों के साथ। इस समस्या को हल करने के लिए, हम शीर्ष u से शुरू करेंगे और सभी आसन्न शीर्षों पर जा

  1. 0-1 BFS (बाइनरी वेट ग्राफ में सबसे छोटा पथ) C प्रोग्राम में? 0-1 BFS (बाइनरी वेट ग्राफ में सबसे छोटा पथ) C प्रोग्राम में?

    मान लीजिए हमारे पास कुछ नोड्स और कनेक्टेड एज वाला एक ग्राफ है। प्रत्येक एज का बाइनरी वेट है। इसलिए वेट या तो 0 या 1 होगा। एक सोर्स वर्टेक्स दिया गया है। हमें सोर्स से किसी भी अन्य वर्टेक्स तक सबसे छोटा पथ ढूंढना है। मान लीजिए ग्राफ नीचे जैसा है: सामान्य BFS एल्गोरिदम में सभी एज वेट समान होते हैं।

  1. फ्लडिंग बनाम फिक्स्ड रूटिंग एल्गोरिदम फ्लडिंग बनाम फिक्स्ड रूटिंग एल्गोरिदम

    फ्लडिंग और फिक्स्ड रूटिंग, इंटरमीडिएट राउटर्स के माध्यम से सोर्स से डेस्टिनेशन तक डेटा पैकेट्स ट्रांसमिट करने की विधियां हैं जो ट्रांसमिशन लाइन्स द्वारा जुड़े होते हैं। फ्लडिंग एक नॉन-एडाप्टिव रूटिंग तकनीक है जो इस सरल विधि का पालन करती है – जब एक डेटा पैकेट राउटर पर आता है, तो उसे उस लिंक को छोड़क