Dijkstra算法
View Code
1 /*
2 The Greedy Approach
3 The Shortest Path Problem
4 Time: 2012-11-19 17:56:57
5 Input: A weighted directed graph G = (V,E), where V = {1,2,...,n}.
6 Output: The distance from vertex 1 to every other vertex in G.
7 */
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <limits.h>
11 #include <stdbool.h>
12
13 typedef struct graph{
14 int **matrix; //图的邻接矩阵
15 int vertex; //图的顶点数
16 int edge; //图的边数
17 }Graph;
18
19 void CreareGraph(Graph *g){
20 //采用邻接矩阵存储结构，构造有向图
21 int vertex, edge;
22 int i, j;
23 int begin, end, weight;
24
25 printf("Please enter the values of vertex and edge:\n");
26 scanf("%d %d", &vertex, &edge);
27 if (vertex>0 && edge > 0){
28 (*g).vertex = vertex;
29 (*g).edge = edge;
30 (*g).matrix = (int **)malloc(sizeof(int *) * (*g).vertex); //为图的邻接矩阵分配空间
31 if (NULL == (*g).matrix){
32 printf("Memory allocation failed. Goodbye.");
33 exit(EXIT_FAILURE);
34 }
35 for (i=0; i<(*g).vertex; ++i){
36 (*g).matrix[i] = (int *)malloc(sizeof(int) * (*g).vertex);
37 if (NULL == (*g).matrix[i]){
38 printf("Memory allocation failed. Goodbye.");
39 exit(EXIT_FAILURE);
40 }
41 }
42
43 for (i=0; i<(*g).vertex; ++i) //初始化矩阵
44 for(j=0; j<(*g).vertex; ++j)
45 (*g).matrix[i][j] = INT_MAX; //将图的顶点间权值初始化为无穷大
46 printf("Please input vertexs and weights between vertexs:\n");
47 for (i=0; i<(*g).edge; ++i){
48 scanf("%d %d %d", &begin, &end, &weight);
49 (*g).matrix[begin][end] = weight;
50 }
51 }
52 else{
53 printf("Illegal vertices or edge number.");
54 exit(EXIT_FAILURE);
55 }
56 }
57
58 void Dijkstra(Graph const *g, int *dist){
59 int i, j;
60 bool *visited = NULL;
61 int min = INT_MAX;
62 int nth;
63
64
65 dist[0] = 0;
66 for (i=1; i<(*g).vertex; ++i)
67 dist[i] = (*g).matrix[0][i];
68 /*for (i=0; i<(*g).vertex; ++i)
69 printf("%d ", dist[i]);
70 putchar('\n');*/
71 visited = (bool *)malloc(sizeof(bool) * (*g).vertex); //记录节点是否被访问过
72 if (NULL == visited){
73 printf("Memory allocation failed. Goodbye.");
74 exit(EXIT_FAILURE);
75 }
76 for (i=0; i<(*g).vertex; ++i) //初始化节点均未被访问过
77 visited[i] = false;
78
79 visited[0] = true;
80 for (i=1; i<(*g).vertex; ++i){
81 for (j=1; j<(*g).vertex; ++j){ //找到最小的dist[j]
82 if (visited[j] == false && dist[j] <= min){
83 min = dist[j];
84 nth = j;
85 }
86 }
87 min = INT_MAX; //min被重新赋值为INT_MAX
88 visited[nth] = true;
89 for (j=1; j<(*g).vertex; ++j){
90 if ( visited[j] == false && //如果该节点尚未被访问
91 (*g).matrix[nth][j]!=INT_MAX && //nth与j节点连通
92 dist[nth]+(*g).matrix[nth][j]<dist[j] ) //且…………
93 dist[j] = dist[nth]+(*g).matrix[nth][j]; //更新dist[j]
94 }
95 }
96 }
97
98 void ShowDist(int const *dist, int n){
99 int i;
100 printf("The Shortest Path(form the first vertex to others):\n");
101 for (i=0; i<n; ++i)
102 printf("%d ", dist[i]);
103 putchar('\n');
104 }
105
106 int main(int argc, char *argv[])
107 {
108 Graph g;
109 int *dist = NULL;
110 int n;
111 int i, j;
112
113 CreareGraph(&g);
114 /*for (i=0; i<g.vertex; ++i)
115 for (j=0; j<g.vertex; ++j)
116 if (g.matrix[i][j] != INT_MAX)
117 printf("%d ", g.matrix[i][j]);
118 putchar('\n');*/
119 dist = (int *)malloc(sizeof(int) * g.vertex); //为存储最短路径的数组分配空间
120 if (NULL == dist){
121 printf("Memory allocation failed. Goodbye.");
122 exit(EXIT_FAILURE);
123 }
124 Dijkstra(&g, dist);
125 n = g.vertex;
126 ShowDist(dist, n);
127
128 free(dist);
129 for (i=0; i<n; ++i)
130 free(g.matrix[i]);
131 free(g.matrix);
132
133 return 0;
134 }
在gcc 4.6.2和visual studio 2012下测试通过