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

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

একটি ডিস্ট্যান্স কলেকশন তৈরি করুন এবং সব ভেরটেক্সের ডিস্ট্যান্স ইনফিনিটি সেট করুন सोур্স নোড বাদে।
সোর্স নোডকে একটি মিন-প্রায়োরিটি কিউতে ০ প্রায়োরিটির সাথে ইনকিউ করুন কারণ ডিস্ট্যান্স ০।
প্রায়োরিটি কিউ খালি না হওয়া পর্যন্ত একটি লুপ শুরু করুন এবং সেটি থেকে মিনিমাম ডিস্ট্যান্সের নোডটি ডিকিউ করুন।
পপ করা নোডের সাথে সংযুক্ত নোডগুলোর ডিস্ট্যান্স আপডেট করুন যদি "current node distance + edge weight < next node distance" হয়, তারপর নতুন ডিস্ট্যান্সের সাথে নোডটিকে কিউতে পুশ করুন।
প্রায়োরিটি কিউ খালি না হওয়া পর্যন্ত চালিয়ে যান।

এই অ্যালগরিদম মূলত অনুমান করে যে সব নোড সোর্স থেকে অনন্ত দূরত্বে। তারপর এটি এজগুলোকে বিবেচনা করতে শুরু করে এবং সোর্স থেকে নোডগুলোর ডিস্ট্যান্স ট্র্যাক রাখে এবং পথে কম খরচের পথ পেলে সেটি আপডেট করে।

আসুন কোডে এর বাস্তবায়ন দেখি:

উদাহরণ

djikstraAlgorithm(startNode) {
    let distances = {};
    // প্রিভিয়াস নোডগুলোর রেফারেন্স সংরক্ষণ করে
    let prev = {};
    let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
    // স্ট্রাট নোড বাদে সব নোডের ডিস্ট্যান্স ইনফিনিটি সেট করুন
    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 }