训练第五周之Dijkstra算法

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
#define INF 99999999 /*我们通常将正无穷定义为99999999，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是2147483647）*/
int road[MAXNUM][MAXNUM];
//题目所给矩阵，有路标权值，无路标INF，本身到本身则标0
long long dist[MAXNUM];
//从v0到vi的最短路径
bool s[MAXNUM];
//表示已经确定了从v0到vi最短路径长度的结点集合
//int pre[MAXNUM];
//如果题目要求输出路线，就用pre来记录前项，本来用的prev结果CE了
int n;
//n为结点个数
void Dijkstra(int v0)
//v0为起点
{
int i,j,u;
for(i=1;i<=n;i++)
{
dist[i]=road[v0][i];
//按题目所给矩阵初始化dist[i]的值
s[i]=false;
//清空集合S
/*if(dist[i] == MAXINT)
//初始化prev[i]值，没有前项则为-1，有则为v0
　　pre[i] = -1;
　　
else
　　pre[i] = v0;*/
}
dist[v0]=0;
s[v0]=true;
//讲v0加入集合S
for(i=2;i<=n;i++)
{
int mindist=INF;
//mindist为v0到U中集合的最短路径长度
int u=v0;
for(j=1;j<=n;j++)
//找到v0到集合U中路径长度最短的结点u
{
if(!s[j]&&dist[j]<mindist)
{
mindist=dist[j];
u=j;
}
}
s[u]=true;
//把u放入集合S中
for(j=1;j<=n;j++)
//更新v0到U中所有点的路径
{
if(!s[j]&&road[u][j]<INF)
if(dist[j]>road[u][j]+dist[u])
{
dist[j]=road[u][j]+dist[u];
//pre[j] = u;
//记录前驱顶点 
}
}
}
}

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 99999999
int road[105][105];
long long dist[105];
bool s[105];
int n,m;
void Dijkstra(int v0)
{
int i,j,u;
for(i=1;i<=n;i++)
{
dist[i]=road[v0][i];
s[i]=false;
}
dist[v0]=0;
s[v0]=true;
for(i=2;i<=n;i++)
{
int mindist=INF;
int u=v0;
for(j=1;j<=n;j++)
{
if(!s[j]&&dist[j]<mindist)
{
mindist=dist[j];
u=j;
}
}
s[u]=true;
for(j=1;j<=n;j++)
{
if(!s[j]&&road[u][j]<INF)
if(dist[j]>road[u][j]+dist[u])
{
dist[j]=road[u][j]+dist[u];
}
}
}
printf("%lldn",dist[n]);
}
int main()
{
int i,j,a,b,c;
while(scanf("%d%d",&n,&m)!=EOF&&(n!=0||m!=0))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(j==i) road[i][j]=0;
else road[i][j]=INF;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
road[a][b]=c;
road[b][a]=c;
}
Dijkstra(1);
}
return 0;
}