यह डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में SSSP (सिंगल सोर्स शॉर्टेस्ट पाथ) खोजने के लिए डिज्क्स्ट्रा एल्गोरिदम का उपयोग करने वाला C++ प्रोग्राम है, जो ग्राफ में पहले नोड से हर दूसरे नोड तक सबसे छोटे पाथ की लंबाई को प्रत्येक वर्टेक्स जोड़ी के साथ दिखाता है।
एल्गोरिदम
Begin ग्राफ के तत्वों को इनपुट के रूप में लें। function shortestpath(): वेरिएबल इनिशियलाइज़ करें a[i] = 1 d[i] = 0 s[i].from = 0 i = 0 से 3 तक लूप इनिशियलाइज़ करें यदि b[0][i] == 0 continue अन्यथा d[i] = b[0][i] s[i].from = 0 done done व्हाइल लूप इनिशियलाइज़ करें जब तक (c < 4) min = INFINITY इनिशियलाइज़ करें i = 0 से 3 तक यदि min <= d[i] या d[i] == 0 या a[i] == 1 continue अन्यथा यदि min > d[i] min = d[i] done क = 0 से 3 तक फॉर लूप यदि (min == d[k]) t = k break अन्यथा continue done a[t] = 1 इनिशियलाइज़ करें j = 0 से 3 तक यदि a[j] == 1 या b[t][j] == 0 continue अन्यथा यदि a[j] != 1 यदि d[j] > (d[t] + b[t][j]) d[j] = d[t] + b[t][j] s[i].from = t done c इन्क्रीमेंट करें done i = 0 से 3 तक फॉर लूप नोड1 से नोड2 तक न्यूनतम लागत प्रिंट करें। done End
उदाहरण
#include <iostream> using namespace std; #define INFINITY 9999 struct node { int from; } s[4]; int c = 0; void djikstras(int *a, int b[][4], int *d) { int i = 0, j, min, t; a[i] = 1; d[i] = 0; s[i].from = 0; for (i = 0; i < 4;i++) { if (b[0][i] == 0) { continue; } else { d[i] = b[0][i]; s[i].from = 0; } } while (c < 4) { min = INFINITY; for (i = 0; i < 4; i++) { if (min <= d[i] || d[i] == 0 || a[i] == 1) { continue; } else if (min > d[i]) { min = d[i]; } } for (int k = 0; k < 4; k++) { if (min == d[k]) { t = k; break; } else { continue; } } a[t] = 1; for (j = 0; j < 4; j++) { if (a[j] == 1 || b[t][j] == 0) { continue; } else if (a[j] != 1) { if (d[j] > (d[t] + b[t][j])) { d[j] = d[t] + b[t][j]; s[i].from = t; } } } c++; } for (int i = 0; i < 4; i++) { cout<<"from node "<<s[i].from<<" cost is:"<<d[i]<<endl; } } int main() { int a[4]; int d[4]; for(int k = 0; k < 4; k++) { d[k] = INFINITY; } for (int i = 0; i < 4; i++) { a[i] = 0; } int b[4][4]; for (int i = 0;i < 4;i++) { cout<<"enter values for "<<(i+1)<<" row"<<endl; for(int j = 0;j < 4;j++) { cin>>b[i][j]; } } djikstras(a,b,d); }
आउटपुट
enter values for 1 row 0 1 3 2 enter values for 2 row 2 1 3 0 enter values for 3 row 2 3 0 1 enter values for 4 row 1 3 2 0 from node 0 cost is:0 from node 0 cost is:1 from node 0 cost is:3 from node 0 cost is:2
