জাভাস্ক্রিপ্টে ফ্লয়েড-ওয়ারশাল অ্যালগরিদম

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

Floyd Warshall অ্যালগরিদম নিম্নরূপ কাজ করে -

• আমরা ইনফিনিটি হওয়ার জন্য দূরত্বের একটি N x N ম্যাট্রিক্স শুরু করি।
• তারপর প্রতিটি প্রান্তের জন্য u, v, আমরা এই প্রান্তের ওজন দেখানোর জন্য এই ম্যাট্রিক্সটি আপডেট করি এবং প্রান্ত v, v এর জন্য আমরা ওজন 0 করে আপডেট করি।
• আমরা I, j এবং k পুনরাবৃত্তিকারীর সাহায্যে 3টি নেস্টেড লুপ তৈরি করি। প্রতিটি নোডের জন্য প্রতিটি নোড j থেকে I এর দূরত্ব, আমরা k ব্যবহারকে মধ্যবর্তী পয়েন্ট হিসাবে বিবেচনা করি এবং দূরত্ব আপডেট করি যদি আমরা বিদ্যমান arr[i][j] থেকে কম পাই।

একটি ম্যাট্রিক্স ব্যবহার করার পরিবর্তে, আমরা একটি বস্তু ব্যবহার করব কারণ প্রতিটি নোডের প্রতিনিধিত্ব করার জন্য আমরা জটিল বস্তু ব্যবহার করলে আমাদের সূচকের ট্র্যাক রাখার দরকার নেই৷

এখন আমরা একই −

উদাহরণ

floydWarshallAlgorithm() {
   let dist = {};
   for (let i = 0; i < this.nodes.length; i++) {
      dist[this.nodes[i]] = {};
      // For existing edges assign the dist to be same as weight
      this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
      this.nodes.forEach(n => {
         // For all other nodes assign it to infinity
         if (dist[this.nodes[i]][n] == undefined)
         dist[this.nodes[i]][n] = Infinity;
         // For self edge assign dist to be 0
         if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
      });
   }
   this.nodes.forEach(i => {
      this.nodes.forEach(j => {
         this.nodes.forEach(k => {
            // Check if going from i to k then from k to j is better
            // than directly going from i to j. If yes then update
            // i to j value to the new value
            if (dist[i][k] + dist[k][j] < dist[i][j])
               dist[i][j] = dist[i][k] + dist[k][j];
            });
         });
      });
      return dist;
   }
}

আপনি −

উদাহরণ

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

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);

console.log(g.floydWarshallAlgorithm());

আউটপুট

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

{
   A: { C: 7, B: 3, D: 4, A: 0 },
   B: { A: 3, B: 0, C: 10, D: 7 },
   C: { A: 7, D: 3, B: 10, C: 0 },
   D: { A: 4, C: 3, B: 7, D: 0 }
}