DAG(방향성 비순환 그래프)에서 SSSP(단일 소스 최단 경로)를 찾는 C++ 프로그램

Dajkstra Algorithm을 사용하여 DAG(Directed Acyclic Graphs)에서 SSSP(Single Source Shortest Path)를 찾는 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