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

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

ফ্লয়েড-ওয়ারশ্যাল অ্যালগরিদম নিচের মতো কাজ করে:

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

ম্যাট্রিক্সের বদলে, আমরা একটি অবজেক্ট ব্যবহার করব কারণ কমপ্লেক্স অবজেক্ট ব্যবহার করে প্রতিটি নোড রিপ্রেজেন্ট করলে আমাদের ইনডেক্স ট্র্যাক রাখতে হয় না।

এখন বাস্তবায়নটি দেখি:

উদাহরণ

floydWarshallAlgorithm() {
    let dist = {};
    for (let i = 0; i < this.nodes.length; i++) {
        dist[this.nodes[i]] = {};
        // বিদ্যমান এজের জন্য ডিস্ট্যান্সকে ওয়েটের সমান করুন
        this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
        this.nodes.forEach(n => {
            // অন্যান্য সব নোডের জন্য ইনফিনিটি অ্যাসাইন করুন
            if (dist[this.nodes[i]][n] == undefined)
                dist[this.nodes[i]][n] = Infinity;
            // সেলফ এজের জন্য ডিস্ট্যান্স ০ অ্যাসাইন করুন
            if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
        });
    }
    this.nodes.forEach(i => {
        this.nodes.forEach(j => {
            this.nodes.forEach(k => {
                // চেক করুন i থেকে k যেতে এবং k থেকে j যেতে কি সরাসরি i থেকে j যাওয়ার চেয়ে ভালো
                // যদি হ্যাঁ হয় তবে i থেকে j ভ্যালুটিকে নতুন ভ্যালুতে আপডেট করুন
                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 }
}