Top

Dijkstra模板 - 最短路


Dijkstra算法是单源最短路算法,最常用时间复杂度(n^2)优化后可以达到(nlogn),不能解决负边问题,稀疏图(点的范围很大但是边不多,边的条数|E|远小于|V|²)需要耗费比较多的空间。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <malloc.h>
#include <cstring>
#include <stack>
#include <cstdio>

//定义邻接矩阵的大小
#define N 100
#define M 100

using namespace std;

typedef struct node {
int map[N][M];//邻接矩阵
int n;//顶点数
int e;//边数
}MGragh;


void dijkstra(MGragh g,int *dis,int *pre,int v0){
int i,j,k;
bool *visited=(bool *)malloc(sizeof(bool)*g.n);//标记数组
for(i=0;i<g.n;i++){//初始化
if(g.map[v0][i]>0&&i!=0){
dis[i]=g.map[v0][i];
pre[i]=v0;
}
else{
dis[i]=INT_MAX;
pre[i]=-1;
}
pre[v0]=v0;
dis[v0]=0;
}
visited[v0]=true;//标记源点v0为访问过
for(i=1;i<g.n;i++){//运行n-1次
int min=INT_MAX;//初始化
int u;
for(j=0;j<g.n;j++){//寻找未访问过的顶点中权值最小的那个
if(visited[j]==false&&dis[j]<min){
min=dis[j];//记录下来
u=j;
}
}
visited[u]=true;//标记为访问过
//更新dis数组的值和路径
for(k=0;k<g.n;k++){
if(visited[k]==false&&g.map[u][k]>0&&g.map[u][k]+min<dis[k]){
dis[k]=min+g.map[u][k];
pre[k]=u;
}
}
}
}

void showpath(int *pre,int v,int v0){//v是当前节点,
//输出源点v0到当前节点v的路径
stack<int>s;
while(v!=v0){
s.push(v);
v=pre[v];
}
s.push(v);
while(!s.empty()){
printf("%d ",s.top());
s.pop();
}
}


int main()
{
int n,e;
while(scanf("%d%d",&n,&e)&&e!=0){
int i,j;
int s,t,w;//起始点s,终点t,边st的权值为w
MGragh g;
int v0;//源点v0
int *dis=(int *)malloc(sizeof(int)*n);//dis[i]记录从源点v0到当前点i的路径长度
int *pre=(int *)malloc(sizeof(int)*n);//记录每个点的前驱,即pre[i]=j;说明i点的前驱为j
for(i=0;i<N;i++){//初始化
for(j=0;j<M;j++){
g.map[i][j]=0;
}
}
g.n=n;
g.e=e;
for(i=0;i<e;i++){//建立邻接矩阵
scanf("%d%d%d",&s,&t,&w);
g.map[s][t]=w;
}
scanf("%d",&v0);

dijkstra(g,dis,pre,v0);
for(i=0;i<n;i++){
if(i!=v0){
showpath(pre,i,v0);//输出路径
printf("%d\n",dis[i]);//输出最短路径的大小
}
}
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址