सी ++ प्रोग्राम सेट का उपयोग करके डिजस्ट्रा के एल्गोरिदम को लागू करने के लिए

यह सेट का उपयोग करके डिजस्ट्रा के एल्गोरिदम को लागू करने के लिए एक सी ++ प्रोग्राम है। यहां हमें दो सेट चाहिए। हम रूट के रूप में दिए गए स्रोत नोड के साथ सबसे छोटा पथ वृक्ष उत्पन्न करते हैं। एक सेट में सबसे छोटे पथ वृक्ष में शामिल शिखर होते हैं और अन्य सेट में शिखर शामिल होते हैं जो अभी तक सबसे छोटे पथ वृक्ष में शामिल नहीं होते हैं। हर कदम पर, हम एक शीर्ष पाते हैं जो दूसरे सेट में है (अभी तक शामिल नहीं है) और स्रोत से न्यूनतम दूरी है।

एल्गोरिदम:

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