यह सेट का उपयोग करके डिज्क्स्ट्रा एल्गोरिदम को इम्प्लीमेंट करने के लिए एक C++ प्रोग्राम है। यहां हमें दो सेट की आवश्यकता होती है। हम दिए गए सोर्स नोड को रूट के रूप में एक शॉर्टेस्ट पाथ ट्री जनरेट करते हैं। एक सेट में शॉर्टेस्ट पाथ ट्री में शामिल वर्टेक्स होते हैं और दूसरा सेट उन वर्टेक्स को शामिल करता है जो अभी तक शॉर्टेस्ट पाथ ट्री में शामिल नहीं हैं। हर चरण में, हम एक ऐसा वर्टेक्स ढूंढते हैं जो दूसरे सेट में है (अभी तक शामिल नहीं किए गए सेट) और सोर्स से न्यूनतम दूरी रखता है।
एल्गोरिदम:
Begin function dijkstra() to find minimum distance: 1) एक सेट Set बनाएं जो शॉर्टेस्ट पाथ ट्री में शामिल वर्टेक्स को ट्रैक करता है, प्रारंभ में, सेट खाली है। 2) इनपुट ग्राफ में सभी वर्टेक्स को एक दूरी मान असाइन किया जाता है। सभी दूरी मानों को INFINITE के रूप में इनिशियलाइज़ करें। सोर्स वर्टेक्स के लिए दूरी मान 0 असाइन किया जाता है ताकि इसे पहले चुना जाए। 3) जब तक Set में सभी वर्टेक्स शामिल नहीं हैं a) एक वर्टेक्स u चुनें जो Set में नहीं है और जिसका न्यूनतम दूरी मान है। b) u को Set में शामिल करें। c) u के सभी आसन्न वर्टेक्स के दूरी मान को अपडेट करें। दूरी मान अपडेट करने के लिए, सभी आसन्न वर्टेक्स के माध्यम से पुनरावृति करें। यदि u के दूरी मान (सोर्स से) और एज u-v के वजन का योग प्रत्येक आसन्न वर्टेक्स v के लिए, v के दूरी मान से कम है, तो v के दूरी मान को अपडेट करें। End
उदाहरण कोड
#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
