ग्राफ सिद्धांत में, सबसे छोटी पथ समस्या एक ग्राफ में दो शीर्षों (या नोड्स) के बीच पथ खोजने की समस्या है जैसे कि इसके घटक किनारों के भार का योग कम से कम हो। यहां हमें अपने ऐड एज को संशोधित करने और किनारों पर वज़न जोड़ने की अनुमति देने के लिए निर्देशित विधियों को जोड़ने की आवश्यकता है।
आइए देखें कि हम इसे कैसे जोड़ सकते हैं -
उदाहरण
/**
* Adds 2 edges with the same weight in either direction
*
* weight
* node1 <================> node2
* weight
*
*/
addEdge(node1, node2, weight = 1) {
this.edges[node1].push({ node: node2, weight: weight });
this.edges[node2].push({ node: node1, weight: weight });
}
/**
* Add the following edge:
*
* 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 का डिफ़ॉल्ट वज़न दिया जाता है। अब हम इसका उपयोग सबसे छोटे पथ एल्गोरिदम को लागू करने के लिए कर सकते हैं।