数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法律学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<<" 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
更新于：30-7 月-2019
2 千+ 次浏览
广告