C ++程序在DAG（有向无环图）中查找SSSP（单源最短路径）

这是一个C ++程序，可使用Dijkstra算法在DAG（有向非循环图）中找到SSSP（单源最短路径），以找出图中的第一个节点到每对顶点旁边显示的最短路径长度的每个其他节点。

算法

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<<" 费用是："<<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 费用是：0
from node 0 费用是：1
from node 0 费用是：3
from node 0 费用是：2