डीएजी (डायरेक्टेड एसाइक्लिक ग्राफ) में एसएसएसपी (सिंगल सोर्स शॉर्टेस्ट पाथ) खोजने के लिए सी ++ प्रोग्राम

यह DAG (डायरेक्टेड एसाइक्लिक ग्राफ़) में SSSP (सिंगल सोर्स शॉर्टेस्ट पाथ) को खोजने के लिए एक C++ प्रोग्राम है, जो ग्राफ़ में पहले नोड से लेकर हर दूसरे नोड तक का पता लगाने के लिए है, जिसमें प्रत्येक जोड़ी के साथ सबसे छोटी पथ लंबाई दिखाई देती है।

एल्गोरिदम

Begin
   Take the elements of the graph as input.
   function shortestpath():
   Initialize the variables
   a[i] = 1
   d[i] = 0
   s[i].from = 0
   Initialize a loop for i = 0 to 3 do
      if b[0][i] == 0
         continue
      else
         d[i] = b[0][i]
         s[i].from = 0
      done
   done
   Initialize a loop while (c < 4)
   initialize min = INFINITY
   for i = 0 to 3 do
      if min <= d[i] or d[i] == 0 or a[i] == 1
         continue
      else if min > d[i]
         min = d[i]
   done
   for loop int k = 0 to 3 do
      if (min == d[k])
         t = k
         break
      else
         continue
      done
      Initialize a[t] = 1
      for j = 0 to 3
         if a[j] == 1 or 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
      done
      Increment c
   done
   For loop i = 0 to 3
      Print minimum cost from node1 to node2.
   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