Dijjkstra

1. #include <iostream>  
2. #include <memory.h>  
3. #include <stdio.h>  
4. using namespace std;  
5.  
6. #define INF 65535  
7.  
8. const int MAXV = 7;  
9. typedef struct{  
10.     int n;  
11.     int edges[MAXV][MAXV];  
12. }Graph;  
13.  
14. // 1  
15. void Dijkstra(Graph graph,  int v);  
16. // 2  
17. void Ppath(int path[], int i, int v);  
18. void Dispath(int dist[], int path[], int s[], int n, int v);  
19.  
20. int main(int argc, char *argv[])  
21. {  
22.     Graph graph;  
23.     int edges[][MAXV] = {  
24.         {0, 4, 6, 6, INF, INF, INF},  
25.         {INF, 0, 1, INF, 7, INF, INF},  
26.         {INF, INF, 0, INF, 6, 4, INF},  
27.         {INF, INF, 2, 0, INF, 5, INF},  
28.         {INF, INF, INF, INF, 0, INF, 6},  
29.         {INF, INF, INF, INF, 1, 0, 8},  
30.         {INF, INF, INF, INF, INF, INF, 0}     
31.     };  
32.     memcpy(graph.edges, edges, MAXV*MAXV*sizeof(int));  
33.     graph.n = MAXV;   
34.     Dijkstra(graph, 0);  
35.     return 0;  
36. }  
37.  
38. // 1  
39. void Dijkstra(Graph graph,  int v)  
40. {  
41.      // put the miniDist   
42.      int dist[MAXV], path[MAXV];  
43.      // put the uses node  
44.      int s[MAXV];  
45.      int mindist, i, j, u;  
46.      // Init  
47.      for(i=0; i<graph.n; i++){  
48.         dist[i] =  graph.edges[v][i];  
49.         s[i] = 0;  
50.         if(graph.edges[v][i]<INF)  
51.             path[i] = v;  
52.         else 
53.             path[i] = -1;     
54.      }  
55.      s[v] = 1;  
56.      path[v] = 0;  
57.      for(i=0; i<graph.n; i++){  
58.           
59.         mindist = INF;  
60.         // 寻找与V点距离最小的点   
61.         for(j=0; j<graph.n; j++){  
62.             if(s[j]==0 && dist[j]<mindist){  
63.                 u = j; // point   
64.                 mindist = dist[j];  
65.             }  
66.         }// end for-j  
67.         // 更新距离  
68.         s[u] = 1;  
69.         if(u==5){  
70.            int temp=3;    
71.         }  
72.         for(j=0; j<graph.n; j++){  
73.             if(s[j]==0){  
74.                 if(graph.edges[u][j]<INF&&dist[u]+graph.edges[u][j]<dist[j]){  
75.                     dist[j] = dist[u] + graph.edges[u][j];  
76.                     path[j] = u;      
77.                 }  
78.             }  
79.         }// end for-j  
80.      }// end for-i  
81.      Dispath(dist, path, s, graph.n, v);  
82.           
83. }  
84.  
85. // 2-1  
86. void Ppath(int path[], int i, int v)  
87. {  
88.     int k;  
89.     k = path[i];  
90.     if(k ==v)  
91.         return;  
92.     Ppath(path, k, v);  
93.     cout<<k<<",";  
94. }  
95.  
96. void Dispath(int dist[], int path[], int s[], int n, int v)  
97. {  
98.     int i;  
99.     for(i=0; i<n; i++){  
100.         if(s[i] ==1){  
101.             printf("从%d到%d的最短路径长度为:%d\t 路径为：", v, i, dist[i]);  
102.             cout<<v<<",";  
103.             Ppath(path, i, v);  
104.             cout<<i<<endl;    
105.         }else{  
106.             printf("从%d到%d不存在路径\n", v, i);    
107.         }  
108.     }  
109. }