Dijkstra算法在C++语言下的实现

 1 #include <iostream>
 2 #include <cstdio>
 3 #define MAXN 1000
 4 #define MAXINT 299999999
 5 
 6 using namespace std; 
 7 
 8 struct Grauph{
 9     int dist[MAXN+10], pre[MAXN+10];
10     bool vis[MAXN+10];
11     int A[MAXN+10][MAXN+10];
12 };
13 Grauph G;
14 int n,m;
15 
16 void init(Grauph &G,int n, int m ){
17     for(int i=0; i<=n; ++ i){
18         G.dist[i] = MAXINT;
19         G.vis[i]  = 1;
20         G.pre[i] = i;
21         for(int j=0;j<=n;++ j) G.A[i][j] = MAXINT; 
22     } 
23 }
24 void Dijkstra(Grauph &G, int s, int n){
25     G.dist[s] = 0;
26     for(int i=0; i<n; ++ i){
27         int k=0;
28         for(int j=1; j<=n; ++ j)
29             if(G.vis[j] && G.dist[j]<G.dist[k]) k = j;
30         G.vis[k] = 0;
31         for(int j=1; j<=n; ++ j)
32             if(G.vis[j] && G.dist[k]+G.A[k][j]<G.dist[j]){
33                 G.dist[j] = G.dist[k] + G.A[k][j]; 
34                 G.pre[j] = k;    
35             } 
36     }
37 }
38 void dfs(int n){
39     if(G.pre[n]==n){
40         printf("%d", n);
41         return;
42     }
43     dfs(G.pre[n]);
44     printf(" -> %d",n);
45     return;
46 }
47 int main(int argc, char** argv) {
48     scanf("%d %d", &n, &m);
49     init(G, n, m);
50     for(int i=0, x, y, w; i<m; ++i){
51         scanf("%d %d %d", &x, &y, &w);
52         if(w<G.A[x][y]){
53             G.A[x][y] = w;
54             G.A[y][x] = w;
55         }
56     }
57     int s = 1;
58     Dijkstra(G, s, n);
59     printf("length(%d -> %d) : %d \n", s, n, G.dist[n]);
60     dfs(n);
61     return 0;
62 }