এখানে একটি গ্রাফ এবং সোর্স ভার্টেক্স দেওয়া থাকে। আমাদের সোর্স ভার্টেক্স থেকে অন্যান্য সব ভার্টেক্স পর্যন্ত সবচেয়ে ছোট পথ বের করতে হবে।
ডিক্সট্রার অ্যালগরিদম হলো একটি লোভী (greedy) অ্যালগরিদম যা গ্রাফের সোর্স ভার্টেক্স থেকে রুট নোড পর্যন্ত সবচেয়ে ছোট পথ খুঁজে বের করে।
অ্যালগরিদম
ধাপ ১: shortPath নামে একটি সেট তৈরি করুন যা শর্টেস্ট পাথ ট্রি-তে আসা ভার্টেক্সগুলো সংরক্ষণ করবে। ধাপ ২: সব দূরত্বের মান ইনফিনিট (INFINITE) হিসেবে আরম্ভ করুন এবং সোর্স ভার্টেক্সের দূরত্ব ০ রাখুন যাতে সেটি প্রথমে বেছে নেওয়া হয়। ধাপ ৩: গ্রাফের সব ভার্টেক্স shortPath-এ আসা পর্যন্ত লুপ চালান। ধাপ ৩.১: একটি নতুন অপ wprowadিত ভার্টেক্স নিন যা সবচেয়ে নিকটে। ধাপ ৩.২: এই ভার্টেক্সটিকে shortPath-এ যোগ করুন। ধাপ ৩.৩: এই ভার্টেক্সের সব সন্নিকট ভার্টেক্সের দূরত্ব আপডেট করুন। প্রতিটি সন্নিকট ভার্টেক্স V এর জন্য, যদি u-এর দূরত্ব এবং এজের ওজনের যোগফল V-এর বর্তমান দূরত্বের চেয়ে কম হয়, তবে আপডেট করুন।
এই অ্যালগরিদম অনুযায়ী একটি প্রোগ্রাম তৈরি করা যাক।
উদাহরণ
#include <limits.h>
#include <stdio.h>
#define V 9
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n) {
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
int main() {
int graph[V][V] = {
{ 0, 6, 0, 0, 0, 0, 0, 8, 0 },
{ 6, 0, 8, 0, 0, 0, 0, 13, 0 },
{ 0, 8, 0, 7, 0, 6, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 6, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 0, 0, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
};
dijkstra(graph, 0);
return 0;
}
আউটপুট
Vertex Distance from Source 0 0 1 6 2 14 3 21 4 21 5 11 6 9 7 8 8 15
