Dijkstra algorithm step by step in C++ Bangla

Dijkstra algorithm step by step in C++ Bangla

কোন নোড থেকে ডেস্টিনেশন নোড এর shortest path বের করার জন্য Dijkstra algorithm  ব্যবহার করা হয়।

                                                       
                                                                                                        



                                                                                                                   



চিত্রে একটি গ্রাফ দেখানো হল যেখানে নোড গুলো মার্কিং করে একটি নোড থেকে আরেকটি নোড এ যাওয়ার cost দেয়া আছে। ধরা যাক 1  থেকে 4  এ যাব। তাহলে  1 থেকে 1---> 2--->4  এ যাওয়া যায় যার total cost=7 । আবার 1---> 3--->4  এ যাওয়া যায়  যার total cost=6 । তাহলে shortest path এর route হবে 1---> 3--->4 এবং ভ্যালু হবে 6 
Dijkstra এর কোড এ আমরা priority_queue use  করব। কারন নোড থেকে সব চেয়ে কম দূরে যেসব নোড আছে তাদের cost  আগে আপডেট করতে হবে।
প্রথমে source, destination, edge number input নিয়ে আমরা এক নোড থেকে আরেক নোড এর ভ্যালু এবং এর সাথে  cost ইনপুট নিবো।
যেহেতু cost ও নেয়া লাগবে দুটি নোড এর ভ্যালুর সাথে তাই শুধু 2D ভেক্টর দিয়ে কাজ হবে না। এর সাথে Pair নিতে হবে।
তাহলে আমরা চিত্র থেকে ইনপুট নেই। 
1    2   5   [ 1 থেকে 2 এ যেতে  cost 5  লাগে] edges[1][0]
1    3   1      edges [1][1]
2    4   2      edges [2][0]
3    4   5      edges [3][0]

vector <pair<int,int> >edges[1000]

priority_queue <pair<int,int>,vector <pair<int,int> >,greater<pair<int,int> > >q;

long long int v1,v2,v3,e,c,i,j,k,l,s,distance,d;

    cin>>s>>d;  // source destination input

    cin>>e;  // number of edge input

    for(i=0;i<e;i++)

    {

        cin>>v1>>v2>>c;  // node value and cost input

        edges[v1].push_back(make_pair(v2,c));

        edges[v2].push_back(make_pair(v1,c));



}

প্রথমে সব নোড এর cost infinity বা বেশি ভ্যালু করে রাখব একটি অ্যারে তে।
memset(sp,10000,sizeof(sp));
প্রথমে সোর্স এ আসার জন্য cost 0 হবে।
sp[s]=0;
তাহলে cost এবং নোড এর ভ্যালু  pair হিসেবে পুশ হবে।
q.push(make_pair(0,s));
Queue: 0 1
এখন এই কিউ থেকে নোড গুলো নিয়ে সেই নোড এর সাথে এডজাসেন্ট নোড গুলোর cost আপডেট করব।
while(!q.empty())

t=q.top(); // top pair of q [0 1]

n1=t.second;  // node of top value which is 1

q.pop();

if(n1==d)

      return sp[n1];
       
     Queue: Empty
     
     for(j=0;j<edges[n1].size();j++)

     {

            n2=edges[n1][j].first;

            w=edges[n1][j].second;


            if(sp[n1]+w<sp[n2])

            {

                sp[n2]=sp[n1]+w;

                q.push(make_pair(sp[n2],n2));

            }

     }


First n1=1  যখন হয় তখন edge[1][0] এর জন্য
N2= edge[1][0] এর প্রথম ভ্যালু 2
W= edges[1][0] এর সেকেন্ড ভ্যালু 5
sp[1]=0 এবং w=5 . তাহলে sp[2]= infinity or 100000. sp[1]+w<sp[2] হল true
sp[2]= 0+5=5. তাহলে 1 to 2 এর cost আপডেট হয়ে 5 হল। এর সাথে কিউ এ cost=5 এবং নোড 2 পুশ করা হল ।
Queue: 5 2
এবার j এর মান 1 বেড়ে edge[1][1] এর জন্য
N2= 3 এবং w=1. তাহলে sp[1]+w=0+1=1 <sp[3]=infinity or 100000
sp[3]=1 । এর সাথে কিউ এ cost=1 এবং নোড 3 পুশ হবে।
Queue: 1 3 ,  5 2
যেহেতু প্রায়োরিটি কিউ এ বলে দেয়া আছে যে সর্ট ডিস্টেন্স কে আগে রাখতে তাই  1 3 আগে চলে আসবে।


এবার যেহেতু কিউ খালি হয় নি তাই আবার while  লুপ এ চলে যাব এবং 1 3 কে টপ এলিমেন্ট হিসেবে নিব।এর সাথে n1 হবে 3.  3 এর এডজাসেন্ট গুলো এখন আপডেট হবে। কিউ এ পপ হবে এর সাথে।
Queue: 5 2
প্রথমে, n1=3 edge[3][0] এর জন্য
N2= edge[3][0].first= 4
W= 5
sp[n1]=sp[3]=1  তাহলে sp[3]+5=1+5=6 < sp[4]=infinity or 10000 .  
sp[4]=6
এবার কিউ এ পুশ হবে 6 4
Queue: 5 2 , 6 4
এবার টপ এলিমেন্ট হিসেবে  5 2 আসবে এবং 2 এর এডজাসেন্ট এর ক্ষেত্রে ওয়েট চেক করবে। এর সাথে কিউ এ পপ হবে।
Queue: 6 4
প্রথমে n1=2 edge[2][0] এর জন্য
N2=edge[2][0].first=4
W=2
Sp[n1]=sp[2]=5 তাহলে sp[2]+2=5+2=7 < sp[4]= 6, কিন্তু এই কন্ডিশন মিথ্যা। তাই sp[2] এর ওয়েট আএ আপডেট হবে না।
এবার টপ এলিমেন্ট হিসেবে 6 4 আসবে এবং কিউ পপ হয়ে খালি হয়ে যাবে।
Queue: Empty
এবার দেখবে  n1=4 যা আমাদের ফাইনাল ডেস্টিনেশন নোড d . তাই sp[n1] এর ভ্যালু রিটার্ন করবে। sp[n1]=sp[4]=6 . সুতরাং আমাদের সর্টেস্ট ডিস্টেন্স ভ্যালু=6

এখন যদি কেউ যে নোড গুলো shortest path এ ইউজ হয়েছে সেগুলো প্রিন্ট করতে চায় তাহলে একটি array নিয়ে n2 কে  array এর ইন্ডেক্স হিসেবে ইউজ করে  n1  এর ভ্যালু রাখলেই আমরা ব্যবহার করা নোডগুলো পেয়ে যাব। এখানে pr[] array  নেয়া হয়েছে। নিচে রিলেটেড প্রব্লেম এর codeforces 20 round  এর problem C এর সলুশন লিঙ্ক দেয়া আছে। সেখানে আউটপুট হিসেবে পাথ ভ্যালু গুলো চাওয়া হয়েছে।

Full Code of Dijkstra algorithm in C++

#include <bits/stdc++.h>
using namespace std;

vector <pair<int,int> >edges[1000];
priority_queue <pair<int,int>,vector <pair<int,int> >,greater<pair<int,int> > >q;
int pr[1000],sp[1000];

int dijkstra(int s, int d)
{
    pair <int,int >t;
    int n1,n2,w,j,k,l;
    memset(sp,10000,sizeof(sp));
    sp[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        t=q.top();
        n1=t.second;
        q.pop();
        //cout<<"n1"<<n1<<endl;
        if(n1==d)
        {
            return sp[n1];
        }
        for(j=0;j<edges[n1].size();j++)
        {
            n2=edges[n1][j].first;
            w=edges[n1][j].second;

            if(sp[n1]+w<sp[n2])
            {
                sp[n2]=sp[n1]+w;
                pr[n2]=n1;

                q.push(make_pair(sp[n2],n2));
            }
        }



    }

   return -1;

}
int main()
{
    long long int v1,v2,v3,e,c,i,j,k,l,s,distance,d;
    cin>>s>>d;
    cin>>e;
    for(i=0;i<e;i++)
    {
        cin>>v1>>v2>>c;
        edges[v1].push_back(make_pair(v2,c));
        edges[v2].push_back(make_pair(v1,c));

    }
    distance = dijkstra(s,d);

    if(distance == -1)
        cout << "There is no link between source and destination\n\n";
    else
    {
        cout << "The distance is " << distance << endl;
    }


    return 0;
}




Related Problems : UVA 10986 Sending Email
                   Codeforces Round 20 Problem C 
 
Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment