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
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
ধন্যবাদ ভাইয়া। এত সুন্দরভাবে বুঝিয়ে লিখার জন্য।
ReplyDeleteThanks. Share this Dijkstra algorithm tutorial with your friends also.
DeleteThis comment has been removed by the author.
ReplyDeleteThank you vaiya...
ReplyDelete