এটি একটি সি++ প্রোগ্রাম যা সেট (Set) ব্যবহার করে ডিকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm) বাস্তবায়ন করে। এখানে আমাদের দুটি সেট দরকার। আমরা দিয়ে गये সোর্স নোড (source node) কে রুট (root) হিসেবে ধরে একটি শর্টেস্ট পাথ ট্রি (shortest path tree) জেনারেট করি। একটি সেটে শর্টেস্ট পাথ ট্রিতে অন্তর্ভুক্ত ভের্টেক্সগুলো থাকে এবং অন্য সেটে এখনো অন্তর্ভুক্ত না হওয়া ভের্টেক্সগুলো থাকে। প্রতিটি স্টেপে, আমরা একটি ভের্টেক্স খুঁজে বের করি যা অন্য সেটে (এখনো অন্তর্ভুক্ত ন হওয়া সেট) আছে এবং সোর্স থেকে যার মিনিমাম দূরত্ব।
অ্যালগরিদম:
শুরু ফাংশন dijkstra() মিনিমাম ডিস্ট্যান্স বের করতে: ১) একটি সেট Set তৈরি করুন যা শর্টেস্ট পাথ ট্রিতে অন্তর্ভুক্ত ভের্টেক্সগুলো ট্র্যাক করে, প্রাথমিকভাবে সেটটি খালি। ২) ইনপুট গ্রাফের সব ভের্টেক্সের জন্য একটি ডিস্ট্যান্স ভ্যালু অ্যাসাইন করুন। সব ডিস্ট্যান্স ভ্যালু INFINITE হিসেবে ইনিশিয়ালাইজ করুন। সোর্স ভের্টেক্সের জন্য ডিস্ট্যান্স ভ্যালু ০ অ্যাসাইন করুন যাতে সেটি প্রথমে পিক করা হয়। ৩) যতক্ষণ Set-এ সব ভের্টেক্স অন্তর্ভুক্ত না হয় ক) একটি ভের্টেক্স u পিক করুন যা Set-এ নেই এবং যার মিনিমাম ডিস্ট্যান্স ভ্যালু। খ) u কে Set-এ অন্তর্ভুক্ত করুন। গ) u-এর সব সংলগ্ন ভের্টেক্সের ডিস্ট্যান্স ভ্যালু আপডেট করুন। ডিস্ট্যান্স ভ্যালু আপডেট করতে, সব সংলগ্ন ভের্টেক্সের মাধ্যমে ইটারেট করুন। যদি u-এর ডিস্ট্যান্স ভ্যালু (সোর্স থেকে) এবং u-v এজের ওয়েটের যোগফল প্রতিটি সংলগ্ন ভের্টেক্স v-র জন্য, v-এর ডিস্ট্যান্স ভ্যালুর চেয়ে কম হয়, তবে v-এর ডিস্ট্যান্স ভ্যালু আপডেট করুন। শেষ
উদাহরণ কোড
#include <iostream> #include <climits> #include <set> using namespace std; #define N 5 int minDist(int dist[], bool Set[])//মিনিমাম ডিস্ট্যান্স ক্যালকুলেট { int min = INT_MAX, min_index; for (int v = 0; v < N; v++) if (Set[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } int printSol(int dist[], int n)//সমাধান প্রিন্ট করুন { cout<<"Vertex Distance from Source\n"; for (int i = 0; i < N; i++) cout<<" \t\t \n"<< i<<" \t\t "<<dist[i]; } void dijkstra(int g[N][N], int src) { int dist[N]; bool Set[N]; for (int i = 0; i < N; i++) dist[i] = INT_MAX, Set[i] = false; dist[src] = 0; for (int c = 0; c < N- 1; c++) { int u = minDist(dist, Set); Set[u] = true; for (int v = 0; v < N; v++) if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v]; } printSol(dist, N); } int main() { int g[N][N] = { { 0, 4, 0, 0, 0 }, { 4, 0, 7, 0, 0 }, { 0, 8, 0, 9, 0 }, { 0, 0, 7, 0, 6 }, { 0, 2, 0, 9, 0 }}; dijkstra(g, 0); return 0; }
আউটপুট
Vertex Distance from Source 0 0 1 4 2 11 3 20 4 26
