描述：小明到小华家有许多条路可以走，现在给出所有能够到达他家的路线，并给出每条线段的长度，求出小明到小华家的最短路线！
介绍第一种学习方法：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
61
62
63
64 |
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<climits>#include<queue>#include<algorithm>using
namespace std;#define N 110#define MAX 999999#define CLR(arr, what) memset(arr, what, sizeof(arr))int
nodenum, edgenum; int
map[N][N], dis[N];bool
visit[N];int
Dijkstra(int
src, int
des){ int
temp, k; CLR(visit, false); int
i = 1 ; for(; i <= nodenum; ++i) dis[i] = (i == src ? 0 : map[src][i]); visit[src] = true; dis[src] = 0; for(i = 1; i<= nodenum; ++i) { temp = MAX; int
j = 1 ; for(; j <= nodenum; ++j) if(!visit[j] && temp > dis[j]) temp = dis[k = j]; if(temp == MAX) break; visit[k] = true; for(j = 1; j <= nodenum; ++j) if(!visit[j] && dis[j] > dis[k] + map[k][j]) dis[j] = dis[k] + map[k][j]; } return
dis[des];}int
main(){ int
start, end, cost; int
answer; while(~scanf("%d%d", &nodenum, &edgenum) && (nodenum + edgenum)) { int
i = 1 ; for(; i <= nodenum; ++i) for(int
j = 1; j <= nodenum; ++j) map[i][j] = MAX; for(i = 1; i <= edgenum; ++i) { scanf("%d%d%d", &start, &end, &cost); if(cost < map[start][end]) map[start][end] = map[end][start] = cost; } answer = Dijkstra(1, nodenum); printf("%d\n", answer); } return
0;} |
原文：http://www.cnblogs.com/scottding/p/3644218.html