迪杰斯特拉算法

 1 #include <iostream>
 2 #include <string.h>
 3 #define INF 1000000     //无穷大
 4 #define MAXN 20         //顶点个数的最大值
 5 
 6 int n;                  //顶点个数
 7 int edge[MAXN][MAXN];   //邻接矩阵
 8 int visited[MAXN];      //用来划分S,T集合的数组(S：已访问集合，T：未访问集合)
 9 int dist[MAXN];         //保存最短路径
10 int path[MAXN];         //保存路径
11 
12 void Dijkstra(int v0)   //求顶点v0到其他顶点的最短路径
13 {
14     for(int i = 0; i < n; ++i) {
15         dist[i] = edge[v0][i];
16         visited[i] = 0;
17         if(i != v0 && dist[i] < INF) path[i] = v0;
18         else path[i] = -1;
19     }
20     visited[v0] = 1;
21     //dist[v0] = 0;
22     //从顶点v0确定n-1条最短路径
23     for(int i = 0; i < n-1; ++i) {
24         int min = INF, u = v0;
25         //在T集合中选择具有最短路径的顶点u
26         for(int j = 1; j < n; ++j) {
27             if(!visited[j] && dist[j] < min) {
28                 u = j;
29                 min = dist[j];
30             }
31         }
32         visited[u] = 1; //将顶点u加入S集合，表示他的最短路径已找到
33         //更新T集合中顶点的dist和path值
34         for(int k = 1; k < n; ++k) {
35             if(!visited[k] && dist[u] + edge[u][k] < dist[k]) {
36                 dist[k] = dist[u] + edge[u][k];
37                 path[k] = u;
38             }
39         }
40     }
41 }
42 
43 int main()
44 {
45     int u, v, w; //边的起点、终点及权值
46     scanf("%d", &n);
47     while(1) {
48         scanf("%d%d%d", &u, &v, &w);
49         if(u == -1 && v == -1 && w == -1) break;
50         edge[u][v] = w;
51     }
52     for(int i = 0; i < n; ++i) {
53         for(int j = 0; j < n; ++j) {
54             if(i == j) edge[i][j] = 0;
55             else if(edge[i][j] == 0) edge[i][j] = INF;
56         }
57     }
58     Dijkstra(0);
59     int shortest[MAXN]; //输出最短路径上的各个顶点时存放各个顶点的序号
60     for(int i = 1; i < n; ++i) {
61         printf("%d\t", dist[i]);    //输出顶点0到顶点i的最短路径长度
62         memset(shortest, 0, sizeof(shortest));
63         int k = 0; 
64         shortest[k] = i;
65         while(path[shortest[k]] != 0) {
66             ++k; shortest[k] = path[shortest[k-1]];
67         }
68         ++k; shortest[k] = 0;
69         for(int i = k; i > 0; --i) 
70             printf("%d->", shortest[i]);
71         printf("%d\n", shortest[0]);
72     }
73     return 0;
74 }