Dijkstra算法

 1 #include<iostream>
 2 using namespace std;
 3 typedef struct Graph
 4 {
 5     public :
 6         int visit[100];
 7         int map[100][100];
 8         int len[100];
 9         int v;
10 }Graph;
11 Graph G;
12 void Init(int N, int M)
13 {
14     G.v = N;
15     for(int i=1; i<=G.v; i++){
16         G.visit[i] = 0;
17         G.len[i] = 0;
18         for(int j=1; j<=G.v; j++){
19             G.map[i][j] = 999;
20         }
21     }
22     
23     int v1, v2, len;
24     for(int i=0; i<M; i++){
25         cin>>v1>>v2>>len;
26         G.map[v1][v2] = len;
27         G.map[v2][v1] = len;
28         //cout<<G.map[v1][v2]<<endl;
29     }
30 }
31 void Dijkstra(int V)
32 {
33     G.visit[V] = 1; // 标记原点已访问
34     
35     for(int i=1; i<=G.v; i++){//初始化各点到原点的距离 
36         G.len[i] = G.map[i][V];
37     }
38     G.len[V] = 0;
39     
40     for(int n=1; n<G.v; n++){//循环 v-1 次，每次找到到已访问的点中最近的路径 
41         int minlen = 999;
42         int k;
43         for(int i=1; i<=G.v; i++){
44             // 每次找到未访问的最近的点 
45             if(G.len[i] < minlen && G.visit[i] == 0){
46                 minlen = G.len[i];
47                 k = i;
48             }
49         
50         }
51         G.visit[k] = 1;// 标记已访问
52         cout<<"K: "<<k<<endl;
53         // 根据找到的最近的点更新到原点的距离 
54         for(int i=1; i<=G.v; i++){
55             if(G.visit[i] == 0 && G.len[i] > G.len[k] + G.map[k][i])
56             G.len[i] = G.len[k] + G.map[k][i];
57         } 
58         
59     }
60 }
61 int main()
62 {
63     // N 表示有几个点， M 表示有几条变， V 表示原点 
64     int N, M, V;
65     
66     cin>>N>>M>>V;
67     Init(N, M);
68     Dijkstra(V);
69     for(int i=1; i<=G.v; i++)
70     cout<<G.len[i]<<" ";
71 } 
72 /* 测试实例 
73 5 6 1
74 1 2 14
75 1 3 2
76 1 4 6
77 2 5 2
78 3 4 3
79 4 5 1
80 */