ডিকস্ট্রার অ্যালগরিদম (অথবা ডিকস্ট্রার শর্টেস্ট পাথ ফার্স্ট অ্যালগরिदম, SPF অ্যালগরিদম) একটি গ্রাফে নোডগুলোর মাঝপথে সবচেয়ে ছোট পথ খুঁজে বের করার জন্য একটি অ্যালগরিদম, যা উদাহরণস্বরূপ রোড নেটওয়ার্ক উপস্থাপন করতে পারে। অ্যালগরিদমটি শুরুর ভার্টেক্স, সোর্স থেকে গ্রাফের অন্যান্য সব পয়েন্ট পর্যন্ত সবচেয়ে ছোট পথের একটি ট্রি তৈরি করে।
ডিকস্ট্রার অ্যালগরিদম একটি সিঙ্গেল সোর্স নোড থেকে শর্টেস্ট পাথ ট্রি খুঁজে বের করে, সোর্স থেকে ন্যূনতম দূরত্বवाले নোডগুলোর একটি সেট তৈরি করে।
গ্রাফের নিম্নলিখিত উপাদান থাকে:
ভার্টেক্স বা নোড, অ্যালগরিদমে v বা u দ্বারা চিহ্নিত।
ওজনযুক্ত এজ যা দুটি নোড সংযুক্ত করে: (u,v) একটি এজ নির্দেশ করে, এবং w(u,v) এর ওজন নির্দেশ করে। ডায়াগ্রামে প্রতিটি এজের ওজন স্লেটি রঙে লেখা আছে।
অ্যালগরিদমের ধাপসমূহ
- সभी ভার্টেক্সের দূরত্ব = ইনফিনিটি সেট করুন, সোর্স ভার্টেক্স ছাড়া, সোর্সের দূরত্ব = 0 সেট করুন।
- সোর্স ভার্টেক্সকে একটি মিন-প্রায়োরিটি কিউতে (দূরত্ব, ভার্টেক্স) ফর্মে পুশ করুন, কারণ মিন-প্রায়োরিটি কিউতে তুলনা ভার্টেক্সের দূরত্ব অনুযায়ী হবে।
- প্রায়োরিটি কিউ থেকে ন্যূনতম দূরত্বযুক্ত ভার্টেক্স পপ করুন (প্রথমে পপ করা ভার্টেক্স = সোর্স)।
- পপ করা ভার্টেক্সের সাথে সংযুক্ত ভার্টেক্সগুলোর দূরত্ব আপডেট করুন যদি "কারেন্ট ভার্টেক্স দূরত্ব + এজ ওজন < নেক্সট ভার্টেক্স দূরত্ব", তাহলে নতুন দূরত্ব সহ ভার্টেক্সটি প্রায়োরিটি কিউতে পুশ করুন।
- যদি পপ করা ভার্টেক্স আগে ভিজিট করা থাকে, তবে এটি ব্যবহার না করে চালিয়ে যান।
- প্রায়োরিটি কিউ খালি না হওয়া পর্যন্ত একই অ্যালগরिदম আবার প্রয়োগ করুন।
একটি গ্রাফ এবং গ্রাফে একটি সোর্স ভার্টেক্স দেওয়া থাকলে, সোর্স থেকে প্রদত্ত গ্রাফের সব ভার্টেক্স পর্যন্ত শর্টেস্ট পথ খুঁজে বের করুন। G[][] গ্রাফ ওজন ম্যাট্রিক্স, n গ্রাফে ভার্টেক্সের সংখ্যা, u শুরুর নোড।
ইনপুট
G[max][max]={{0,1,0,3,10}, {1,0,5,0,0}, {0,5,0,2,1}, {3,0,2,0,6}, {10,0,1,6,0}} n=5 u=0
আউটপুট
Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
ব্যাখ্যা
এডজেসেন্সি ম্যাট্রিক্স adj[][] থেকে কস্ট ম্যাট্রিক্স C[][] তৈরি করুন। C[i][j] হলো ভার্টেক্স i থেকে ভার্টেক্স j-এ যাওয়ার খরচ। যদি ভার্টেক্স i এবং j-এর মাঝপথে কোনো এজ না থাকে তবে C[i][j] ইনফিনিটি।
ভিজিটেড অ্যারে [] শূন্যে ইনিশিয়ালাইজ করা হয়।
for(i=0;i<n;i++) visited[i]=0;
যদি ভার্টেক্স ০ সোর্স ভার্টেক্স হয় তবে visited[0] ১ হিসেবে মার্ক করা হয়।
ডিস্ট্যান্স ম্যাট্রিক্স তৈরি করুন, সোর্স ভার্টেক্স ০ থেকে n-1 পর্যন্ত ভার্টেক্সগুলোর খরচ সংরক্ষণ করে।
for(i=1;i<n;i++) distance[i]=cost[0][i];
শুরুতে, সোর্স ভার্টেক্সের দূরত্ব ০ ধরা হয়। অর্থাৎ distance[0]=0;
for(i=1;i<n;i++) visited[i]=0;
একটি ভার্টেক্স w নির্বাচন করুন, যাতে distance[w] ন্যূনতম এবং visited[w] 0। visited[w] ১ হিসেবে মার্ক করুন।
শেষ একই থেকে বাকি ভার্টেক্সগুলোর শর্টেস্ট দূরত্ব পুনরায় গণনা করুন।
শুধু যেসব ভার্টেক্স visited[] অ্যারেতে ১ হিসেবে মার্ক করা নেই, সেগুলো দূরত্ব পুনরায় গণনার জন্য বিবেচনা করা হবে। অর্থাৎ প্রতিটি ভার্টেক্স v-এর জন্য
if(visited[v]==0) distance[v]=min(distance[v], distance[w]+cost[w][v])
উদাহরণ
#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}
