ग्राफ थ्योरी में, शॉर्टेस्ट पाथ समस्या एक ग्राफ में दो वर्टेक्स (या नोड्स) के बीच एक पाथ खोजने की समस्या है जैसे कि इसके घटक एजेज के वजन का योग न्यूनतम हो। यहां हमें अपने 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 असाइन किया जाता है। अब हम इसका उपयोग शॉर्टेस्ट पाथ एल्गोरिदम लागू करने के लिए कर सकते हैं।