জাভাস্ক্রিপ্টে শর্টেস্ট পাথ অ্যালগরিদম

গ্রাফ থিওরিতে, শর্টেস্ট পাথ সমস্যা হলো একটি গ্রাফে দুটি ভারটেক্স (বা নোড) এর মধ্যে একটি পাথ খুঁজে বের করার সমস্যা যাতে তার কনস্টিটুয়েন্ট এজগুলোর ওয়েটের যোগফল মিনিমাইজ করা যায়। এখানে আমাদের add edge এবং add directed মেথডগুলো মডিফাই করতে হবে যাতে এজগুলোর সাথে ওয়েট যোগ করা যায়।

আসুন দেখি কীভাবে এটি যোগ করা যায়:

উদাহরণ

/**
 * একই ওয়েটের সাথে দুটি এজ দুই দিকে যোগ করে
 * 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 });
}
/**
 * নিচের এজটি যোগ করুন:
 * 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);
}

এখন যখন আমরা আমাদের গ্রাফে একটি এজ যোগ করব, যদি আমরা ওয়েট স্পেসিফাই না করি, তবে সেই এজের জন্য ডিফল্ট ওয়েট ১ অ্যাসাইন হবে। এখন আমরা এটিকে ব্যবহার করে শর্টেস্ট পাথ অ্যালগরिदম বাস্তবায়ন করতে পারি।