সেট ব্যবহার করে ডিজকস্ট্রার অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

এটি সেট ব্যবহার করে Dijkstra এর অ্যালগরিদম বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম। এখানে আমাদের দুটি সেট থাকতে হবে। আমরা মূল হিসাবে প্রদত্ত উত্স নোড সহ একটি সংক্ষিপ্ত পথ গাছ তৈরি করি। একটি সেটে শীর্ষবিন্দু রয়েছে সংক্ষিপ্ততম পথ গাছে এবং অন্য সেটে শীর্ষবিন্দুগুলি রয়েছে যা এখনও সংক্ষিপ্ততম পথ গাছে অন্তর্ভুক্ত হয়নি। প্রতিটি ধাপে, আমরা একটি শীর্ষবিন্দু খুঁজে পাই যা অন্য সেটে রয়েছে (সেট এখনও অন্তর্ভুক্ত নয়) এবং উত্স থেকে ন্যূনতম দূরত্ব রয়েছে৷

অ্যালগরিদম:

Begin
   function dijkstra() to find minimum distance:
   1) Create a set Set that keeps track of vertices included in shortest
   path tree, Initially, the set is empty.
   2) A distance value is assigned to all vertices in the input graph.
   Initialize all distance values as INFINITE. Distance value is assigned as
   0 for the source vertex so that it is picked first.
   3) While Set doesn’t include all vertices
      a) Pick a vertex u which is not there in the Set and has minimum distance value.
      b) Include u to Set.
      c) Distance value is updated of all adjacent vertices of u.
      For updating the distance values, iterate through all adjacent
      vertices. if sum of distance value of u (from source) and weight of
      edge u-v for every adjacent vertex v, is less than the distance value
      of v, then update the distance value of v.
End

উদাহরণ কোড

#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5
int minDist(int dist[], bool Set[])//calculate minimum distance
{
   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)//print the solution
{
   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