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