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

ডিজকস্ট্রার অ্যালগরিদম হল একটি ওজনযুক্ত গ্রাফে নোডগুলির মধ্যে সংক্ষিপ্ততম পথগুলি খুঁজে বের করার জন্য একটি অ্যালগরিদম৷ গ্রাফ তৈরি করার সময় আমরা প্রান্তে ওজন যোগ করতে নতুন addEdge এবং addDirectedEdge পদ্ধতি ব্যবহার করব। আসুন দেখি কিভাবে এই অ্যালগরিদম কাজ করে −

• একটি দূরত্ব সংগ্রহ তৈরি করুন এবং উৎস নোড ব্যতীত সমস্ত শীর্ষের দূরত্বকে অসীম হিসাবে সেট করুন৷
• উৎস নোডটিকে একটি ন্যূনতম-অগ্রাধিকার সারিতে সারিবদ্ধ করুন অগ্রাধিকার 0 সহ কারণ দূরত্ব 0।
• অগ্রাধিকার সারি খালি না হওয়া পর্যন্ত একটি লুপ শুরু করুন এবং এটি থেকে ন্যূনতম দূরত্ব সহ নোডটিকে সারিবদ্ধ করুন৷
• পপড নোডে সংযুক্ত নোডের দূরত্ব আপডেট করুন যদি "বর্তমান নোড দূরত্ব + প্রান্ত ওজন <পরবর্তী নোড দূরত্ব", তারপর সারিতে নতুন দূরত্ব সহ নোডটিকে ঠেলে দিন৷
• অগ্রাধিকার সারি খালি না হওয়া পর্যন্ত চালিয়ে যান।

এই অ্যালগরিদমটি মূলত যা করে তা হল অনুমান করে যে সমস্ত নোড উৎস থেকে অসীম দূরত্বে রয়েছে। তারপরে এটি প্রান্তগুলিকে বিবেচনায় নেওয়া শুরু করে এবং উত্স থেকে নোডের দূরত্বের ট্র্যাক রাখে যদি এটি পথে একটি কম খরচের পথ খুঁজে পায় তবে একই আপডেট করে৷

আসুন কোড −

উদাহরণ

djikstraAlgorithm(startNode) {
   let distances = {};

   // Stores the reference to previous nodes
   let prev = {};
   let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

   // Set distances to all nodes to be infinite except startNode
   distances[startNode] = 0;
   pq.enqueue(startNode, 0);
   this.nodes.forEach(node => {
      if (node !== startNode) distances[node] = Infinity;
      prev[node] = null;
   });

   while (!pq.isEmpty()) {
      let minNode = pq.dequeue();
      let currNode = minNode.data;
      let weight = minNode.priority;
      this.edges[currNode].forEach(neighbor => {
         let alt = distances[currNode] + neighbor.weight;
         if (alt < distances[neighbor.node]) {
            distances[neighbor.node] = alt;
            prev[neighbor.node] = currNode;
            pq.enqueue(neighbor.node, distances[neighbor.node]);
         }
      });
   }
   return distances;
}

আপনি −

উদাহরণ

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);

console.log(g.djikstraAlgorithm("A"));

আউটপুট

এটি আউটপুট দেবে −

{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }