Dijkstra算法记录最短路径 | Eternal_zttz

Dijkstra算法记录最短路径

用dijkstra算法来记录最短路径方法,用一个数组path[]记录前驱顶点,找到最短路后,从终点倒向追踪,直到找到起点为止。这里可以利用栈来记录路径倒推的过程.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
#define N 1001
#define M 50001
#define INF 99999999
int n,m,s,t1,t2,t3;;
int dis[N],tim[N];
bool vis[N];
int e[N][N];
int pre[N];
void dijkstra(){
for (int i = 1;i<=n;i++){
dis[i] = e[s][i];
vis[i] = false;
pre[i] = dis[i]!=INF&&i!= s? s:-1;
}
vis[s] = true;
int u =1;
for (int i =1;i<=n;i++){
int min = INF;
for (int j =1;j<=n;j++){
if(!vis[j]&&dis[j]<min){
min = dis[j];
u = j;
}
}
vis[u] = true;
for (int v = 1;v<=n;v++){
if(e[u][v]<INF){
if(!vis[v]&&dis[v]>dis[u]+e[u][v]){
dis[v] = dis[u] +e[u][v];
pre[v] = u;
}
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
if(n ==00&&m==0) return 0;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
for (int i = 1;i<=n;i++){
for (int j = 1;j<=n;j++)
e[i][j] = i==j? 0:INF;
}
for (int i = 1;i<=m;i++){
scanf("%d %d %d",&t1,&t2,&t3);
if(e[t1][t2]>t3)
e[t1][t2] = t3;
}
int start ,end;
while(~scanf("%d %d",&start,&end)){
s = start;
dijkstra();
if(start == end){
printf("从%d到%d的最短路径是:%d\n",start,end,start);
printf("最短路径:%d\n",0);
}else{
stack<int> path;
path.push(end);
int now = pre[end];
while(1){
path.push(now);
if(now == start)
break;
now = pre[now];
}
printf("从%d到%d的最短路线是:%d",start,end,start);
path.pop();
while(!path.empty()){
printf("-->%d",path.top());
path.pop();
}
printf("\n");
printf("最短路径:%d\n",dis[end]);
}
}
}

程序输入:

1
2
3
4
5
6
7
8
9
10
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
4 3

程序输出:

1
2
从4到3的最短路线是:4-->1-->2-->3
最短路径:10

-------------The End-------------