首页 > 编程语言 > 详细

图中最短路径的算法--dijiska算法C语言实现

时间:2017-10-14 23:07:09      阅读:473      评论:0      收藏:0      [点我收藏+]
技术分享
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define ERROR_NO_MEM   -1   /*内存不足的错误码*/
  5 
  6 #define MAX_POINT_NUM   5  /*最大的点数*/
  7 #define MAX_EDGE_NUM  7    /*最多的边数*/
  8 
  9 #define MAX_VALUE  0xfffffff  /*最大路径长度*/
 10 
 11 /*表示每个结点的信息*/
 12 struct tagEdgeNode 
 13 {
 14     int value;             /*结点数值*/
 15     struct tagEdgeNode *next;  /*指向路径的下一个结点*/
 16 };
 17 
 18 /*存储路径的数组*/
 19 typedef struct tagEdgeNode *adjlist[MAX_POINT_NUM];
 20 
 21 
 22 /*存储图的邻接矩阵*/
 23 typedef int AdjMatrix[MAX_POINT_NUM ][MAX_POINT_NUM ];
 24 
 25 
 26 /*
 27 释放链表上的动态内存 
 28 */
 29 void freeNode(struct tagEdgeNode *list)
 30 {
 31         struct tagEdgeNode *p = NULL;
 32         struct tagEdgeNode *tmp = NULL;
 33         
 34         p = list;
 35         while(NULL != p)
 36         {
 37                 tmp = p->next;
 38                 
 39                 free(p);
 40                 
 41                 p = tmp;
 42         }
 43         
 44         return ;
 45 }
 46 
 47 /*
 48 显示图的邻接矩阵 
 49 */
 50 void showGraph(AdjMatrix GA)
 51 {
 52     int i;
 53     int j;
 54     
 55     for(i = 0; i < MAX_POINT_NUM; i++)
 56     {
 57         for(j = 0; j < MAX_POINT_NUM; j++)
 58         {
 59                 if(( MAX_VALUE != GA[i][j] ) && ( 0 != GA[i][j] ))
 60                 {
 61                         printf("GA[%d][%d] =%d \r\n", i, j, GA[i][j]);
 62                         }
 63             
 64         }
 65         
 66         printf("\r\n");
 67     }
 68 
 69     return ;
 70 }
 71 
 72 
 73 
 74 /*
 75 修改路径结点 
 76 */
 77 int ChangePath(adjlist path, int m, int j)
 78 {
 79     struct tagEdgeNode *p = NULL;
 80     struct tagEdgeNode *q = NULL;
 81     struct tagEdgeNode *end = NULL;
 82     
 83     /*清除顶点j的当前最短路径*/
 84     freeNode(path[j]);
 85     path[j] = NULL;
 86 
 87     /*把到顶点m的最短路径复制到顶点j的最短路径上*/
 88     p = path[m];
 89     while(NULL != p)
 90     {
 91         q = malloc(sizeof(struct tagEdgeNode));
 92         if(NULL == q)
 93         {
 94                 /*申请内存失败,释放已有链表*/
 95                 freeNode(path[j]);
 96                 return ERROR_NO_MEM;
 97                 }
 98 
 99         q->value = p->value;
100         if( NULL == path[j] )
101         {
102             path[j] = q;
103         }
104         else
105         {
106             end->next = q;
107         }
108 
109         end = q;
110         p = p->next;
111     }
112 
113     /*把顶点j加入到path[j]单链表的最后,形成新的目前最短路径*/
114     q = malloc(sizeof(struct tagEdgeNode));
115     if(NULL == q)
116     {
117         /*申请内存失败,释放已有链表*/
118         freeNode(path[j]);
119         return ERROR_NO_MEM;
120         }
121         
122     q->value = j;
123     q->next = NULL;
124     
125     end->next = q;
126 
127     return 0;
128 }
129 
130 
131 
132 /*
133 查找出从节点i开始到其他所有节点的最短路径(dijkstra算法) 
134 */
135 int FindShortestPath(AdjMatrix GA, int dist[], adjlist path, int i)
136 {
137     int j, k,w,m;
138     int newDistance;
139     int minDistance;
140     
141     int Set[MAX_POINT_NUM];  /*存放已求得最短路径的节点*/
142     struct tagEdgeNode *p1 = NULL;
143     struct tagEdgeNode *p2 = NULL;
144 
145         /*初始化Set集合、路径结点集合*/
146     for(j =0; j < MAX_POINT_NUM; j++)
147     {
148         if( j == i )
149         {
150             Set[j] = 1;
151         }
152         else
153         {
154             Set[j] = 0;
155         }
156 
157         dist[j] = GA[i][j];
158 
159                 /*如果到相邻结点的距离不是无穷大,则记录该路径*/
160         if(( dist[j] < MAX_VALUE ) && ( j != i))
161         {
162                 p1 = malloc(sizeof(struct tagEdgeNode));
163                 p2 = malloc(sizeof(struct tagEdgeNode));
164                 if(( NULL == p1) || ( NULL == p2 ))
165                 {
166                         if( NULL != p1 )  
167                         {
168                                 free(p1);
169                                 }
170                                 if( NULL != p2 )
171                                 {
172                                         free(p2);
173                                 }
174                                 
175                                 return ERROR_NO_MEM;
176                         }
177         
178             p1->value = i;
179             p2->value = j;
180             p2->next = NULL;
181             p1->next = p2;
182             path[j] = p1;
183         }
184         else
185         {
186             path[j] = NULL;
187         }            
188     }
189 
190     /*共计需要n-2次循环, 每次循环选择路径最短的作为起点*/
191     for ( k = 1; k <= MAX_POINT_NUM-2; k++)
192     {
193         /*求出第k个终点m*/
194         minDistance = MAX_VALUE;
195         m = i;
196 
197                 /*寻找到下一个开始搜寻的节点:条件是不在集合中,而且距起始节点最近*/
198         for(j = 0; j < MAX_POINT_NUM; j++)
199         {
200             if(( Set[j] == 0 ) && (dist[j] < minDistance))
201             {
202                 minDistance = dist[j];
203                 m = j;
204             }
205         }
206 
207         /*若条件成立, 则把顶点m并入集合S中, 否则退出循环,因为剩余的顶点, 
208           其最短路径长度均为MAX_VALUE,无需再计算*/
209         if( m != i)
210         {
211             Set[m] = 1;
212         }
213         else
214         {
215             break;
216         }
217 
218         /*从未排序节点中选择对应dist和path中的元素做必要修改*/
219         for( j = 0; j < MAX_POINT_NUM; j++)
220         {
221                 newDistance = dist[m] + GA[m][j];
222             if(( 0 == Set[j] ) && ( newDistance < dist[j] ))
223             {
224                 dist[j] = newDistance;
225                 ChangePath(path, m, j);
226             }
227         }
228     }
229 
230     /*显示图的最短距离和最短路径*/
231     printf("next show shortest path as following: \r\n");
232     for(i = 0; i < MAX_POINT_NUM; i++)
233     {
234         printf("min distance to [%d] = %d \r\n", i, dist[i]);
235         printf("path:");
236         
237         p1 = path[i];
238         while(NULL != p1)
239         {
240                 printf(" %d ", p1->value);
241                 p1 = p1->next;
242                 }
243                 
244                 printf("\r\n\r\n");
245     }
246     
247     /*释放所有的动态内存*/ 
248     for(i = 0; i < MAX_POINT_NUM; i++)
249     {
250         freeNode(path[i]);
251         }
252     
253     return 0;
254 }
255 
256 
257 /*
258   创建图的邻接矩阵。
259   创建成功时,返回0. 
260   创建失败时,返回错误码
261   */
262 int createGraph(AdjMatrix GA)
263 {
264     int i;
265     int j;
266     int k;
267     int weigt;
268     
269 
270     /*初始化邻接数组*/
271     for(i = 0; i < MAX_POINT_NUM; i++)
272     {
273         for(j = 0; j < MAX_POINT_NUM; j++)
274         {
275             if( i == j)
276             {
277                 GA[i][j] = 0;
278             }
279             else
280             {
281                 GA[i][j] = MAX_VALUE;
282             }
283         }
284     }
285 
286     /*建立邻接数组*/
287     printf("input number from 0 to 4 as edge point. and max 7 link between those points. weigt should less than 0xfffffff\r\n");
288     printf("input one edge, from i to j, weigh, format is: i j weigt \r\n");
289     for(k = 1; k <= MAX_EDGE_NUM; k++ )
290     {
291         /*建立一条边。从i到j. 权值为w <i  j  w>*/
292         
293         scanf("%d %d %d", &i, &j, &weigt);
294         
295         /*判断参数合法性*/
296         if(( i > 4 ) || ( j > 4) || (weigt >= MAX_VALUE))
297         {
298                 printf("invalid i or j or weigt value. i=%d j=%d weigt=%d \r\n", i, j, weigt);
299                 continue;
300                 }
301 
302         GA[i][j] = weigt;
303     }
304     
305 /*  可以用下面这组作为测试数据,验证算法 
306     GA[0][1] = 1;
307     GA[0][2] = 2;
308     GA[1][2] = 3;
309     GA[1][3] = 1;
310     GA[1][4] = 3;
311     GA[3][4] = 1;
312     GA[2][4] = 2;
313 */    
314 
315     return 0;
316 }
317 
318 
319 
320 
321 int main()
322 {
323     int ret;
324     AdjMatrix GA;
325     adjlist path;
326     int dist[MAX_POINT_NUM];
327 
328     ret = createGraph(GA);
329     if( 0 != ret)
330     {
331         printf("error. fail to create Graph");
332         return 1;
333     }
334 
335     showGraph(GA);
336 
337     ret = FindShortestPath(GA, dist, path, 0);
338     if( 0 != ret)
339     {
340         printf("error. can not find the short path from point 0 in Graph");
341         return 1;
342     }
343 
344     return 0;
345 }
View Code

 

图中最短路径的算法--dijiska算法C语言实现

原文:http://www.cnblogs.com/zhouhaibing/p/7668823.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!