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

গ্রাফ তত্ত্বে, সংক্ষিপ্ততম পথের সমস্যা হল একটি গ্রাফে দুটি শীর্ষবিন্দুর (বা নোড) মধ্যে একটি পথ খুঁজে বের করার সমস্যা যাতে এর উপাদান প্রান্তের ওজনের যোগফলকে ন্যূনতম করা হয়। এখানে আমাদের অ্যাড এজ পরিবর্তন করতে হবে এবং প্রান্তে ওজন যোগ করার জন্য নির্দেশিত পদ্ধতি যোগ করতে হবে।

আসুন দেখি কিভাবে আমরা এই −

উদাহরণ

/**
   * 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 এর একটি ডিফল্ট ওজন নির্ধারণ করা হয়। আমরা এখন সংক্ষিপ্ততম পাথ অ্যালগরিদম প্রয়োগ করতে এটি ব্যবহার করতে পারি।