Chương trình C ++ để tìm SSSP (Đường dẫn ngắn nhất nguồn duy nhất) trong DAG (Đồ thị mạch vòng được hướng dẫn)

Đây là một chương trình C ++ để tìm SSSP (Đường dẫn ngắn nhất nguồn đơn) trong DAG (Đồ thị vòng có hướng dẫn) bằng cách sử dụng Thuật toán Dijkstra để tìm ra từ nút đầu tiên trong biểu đồ đến mọi nút khác có độ dài đường dẫn ngắn nhất được hiển thị bên cạnh mỗi cặp đỉnh.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

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