单源最短路径
程序员文章站
2022-04-18 21:27:52
如果不了解单源最短路径问题可以自行百度或参考算法书籍，这里只给出一种解法，对问题本身不做详细介绍 在以下求解单源最短路径问题的代码中使用了重要的核心函数Findroad，它是求解该问题的基础,用它可以找出图中两顶点间的所有路径,Findroad配合筛选路径的SOperate函数即可找出最短路径.同时 ......
如果不了解单源最短路径问题可以自行百度或参考算法书籍，这里只给出一种解法，对问题本身不做详细介绍
在以下求解单源最短路径问题的代码中使用了重要的核心函数Findroad，它是求解该问题的基础,用它可以找出图中两顶点间的所有路径,Findroad配合筛选路径的SOperate函数即可找出最短路径.同时还使用了Fillr函数填充r矩阵,建立源顶点结构体数组,这样求解单源最短路径问题时可以少走一些歪路。Fillr函数中使用了Length递归函数求两顶点间最短路径长度，帮助判断连接两顶点的边是否为最短路径。Length函数求最短路径长度用到了一个基本事实：与图中某起始顶点有边相连的其他所有顶点到终点的最短路径和这些顶点到起始顶点的边组成的路径中长度最小的路径即为起始顶点到终点的最短路径。
以下是具体的C语言代码：
1 #include <stdio.h>
2 #include <malloc.h>
3 #define N 7 //无环单边非负权重无向图顶点数
4
5 struct Order //表示除源顶点外其他顶点参数的结构体类型
6 {
7 int col; //顶点标号
8 int weight; //源顶点到顶点的权重
9 int mark;
10 };
11 typedef struct Order Order1;
12
13 struct Link //表示除源顶点外其他到源顶点权重不为零的顶点的结构体类型
14 {
15 int col; //顶点标号
16 int weight; //源顶点到顶点的权重
17 int mark;
18 struct Link *next;
19 };
20 typedef struct Link Link1;
21
22 struct Path //表示路径节点的结构体类型
23 {
24 int sign; //节点代表的顶点的标号
25 int next; //路径中与当前顶点相连的下一顶点的标号
26 struct Path *pnext;
27 struct Path *pbefore;
28 };
29 typedef struct Path Path1;
30
31 struct assist //表示已搜索出的路径中的节点的结构体类型
32 {
33 int tab; //顶点标号
34 struct assist *next;
35 };
36 typedef struct assist assist1;
37
38 struct Shortest //用来指向已搜索出的路径的结构体类型
39 {
40 struct Shortest *pbe; //指向自身类型的节点的指针
41 struct assist *passist; //指向存放已搜索出的路径的链表的指针
42 };
43 typedef struct Shortest Shortest1;
44
45 void Fillr(int m, int p[][N], int q[][N], int r[][N], int z[][N], Order1 *Svertex, int *k); //该函数用于填充表示顶点对连线是否为顶点对之间最短路径的矩阵，同时在该函数中建立源顶点结构体数组，和求出源顶点数组中权重为零的节点的最大标号
46 int Length(int start, int end, int q[][N], int z[][N], int node[]); //求start和end顶点之间的最短路径长度的递归函数,当最短路径存在时返回其长度，不存在时返回零
47 void insert(Link1 *headm, Link1 *psnewm); //函数,用于将psnewm指向的Link型节点按插入排序的方式插入至Link型链表中
48 int Enable(int i, int j, int p[][N], int r[][N], int z[][N], int node[]); //函数，用于判定由顶点i是否可以前进至顶点j,可以返回1， 否则返回0
49 int Search(int k, int option, int p[][N], int r[][N], int z[][N], int node[]); //在顶点k上依次搜索option顶点后的第一个可达的顶点，搜索成功返回顶点标号，否则返回-1
50 void FindRoad(int start, int end, int m, int p[][N], int q[][N], int r[][N], int z[][N], int *spo, Shortest1 **heads, Shortest1 **tail, int k1, int p1); //路径搜索函数,用于搜索start和end两节点间的路径
51 void Delete(Shortest1 **heads, Shortest1 **tail); //删除搜索到的所有路径
52 Shortest1 *Copy(Path1 *headp); //拷贝找到的路径
53 void SOperate(int *spo, Shortest1 **heads, Shortest1 **tail, int k, int m, int r[][N], int q[][N], int RoadLength, Path1 *headp, int p); //求最短路径的函数
54 void SOutput(int *spo, Shortest1 **heads, Shortest1 **tail, int k, int m, int r[][N], int q[][N]); //输出顶点k+1到m的所有最短路径
55 //源顶点就是单源最短路径中求路径的起始点
56 //源顶点结构体数组即为表示源顶点和其他非源顶点组成的顶点对的结构体变量组成的数组，每一个结构体变量储存了相应的顶点对的权重，顶点对中非源顶点的标号
57 void main()
58 {
59 int i, j, m, k, flag; //m为源顶点标号,k为源顶点数组中权重为零的节点的最大标号
60 int p[N][N], q[N][N], r[N][N], z[N][N]; /*p为单边非负权重无向无环图的邻接矩阵，q为(i,j)元为顶点i+1和顶点j+1连线的权重的权重矩阵,r为(i,j)元表示连接顶点i+1和顶点j+1的边是否为最短路径(0,表示没有边连接,1表示边非最短路径,2表示边为最短路径)的矩阵,z为标记边(i+1,j+1)是否已被访问(1已访问,0未访问)的矩阵*/
61 int spo; //最短路径长度
62 char t[N+1];
63 Order1 swap;
64 Order1 Svertex[N-1]; //源顶点结构体数组
65 Shortest1 *head, *tail;
66
67 head=(Shortest1 *) malloc(sizeof(Shortest1)); //初始化Shortest1类型链表
68 tail=head;
69 head->pbe=NULL;
70 head->passist=NULL;
71
72 printf("请输入图的N阶邻接矩阵\n");
73 for (i=0; i<N; i++)
74 {
75 printf("请输入邻接矩阵的第%d行\n", i+1);
76 scanf ("%s", t); //输入邻接矩阵
77
78 for (j=0; j<N; j++)
79 p[i][j]=t[j]-48;
80 }
81
82 printf("请输入图的N阶权重矩阵\n");
83 for (i=0; i<N; i++)
84 {
85
86 printf("请输入权重矩阵的第%d行\n", i+1);
87 scanf ("%s", t); //输入权重矩阵
88
89 for (j=0; j<N; j++)
90 q[i][j]=t[j]-48;
91 }
92
93 printf("请输入单源最短路径问题中的源顶点标号:\n");
94 scanf("%d", &m); //输入源顶点标号
95
96 for (i=0; i<N; i++) /*建立r矩阵并初始化对角线*/
97 {
98 r[i][i]=0;
99 }
100
101 for (i=0; i<N; i++) /*建立z矩阵并初始化为0*/
102 {
103 for (j=0; j<N; j++)
104 z[i][j]=0;
105 }
106
107 Fillr(m, p, q, r, z, Svertex, &k); /*填充r矩阵，建立实例化源顶点数组求，最源顶点数组中权重为零的节点的最大标号*/
108
109 if (m==N) /*m=N时执行Fillr函数时源顶点数组没有实例化，源顶点数组中权重为零的节点的最大标号也没有求出,所以就在这里实例化并计算,供求单源最短路径时使用*/
110 {
111 for (i=0; i<N-1; i++)
112 {
113 Svertex[i].col=i; //实例化源顶点数组
114 Svertex[i].weight=q[N-1][i];
115 }
116
117 for (i=1; i<N-1; i++)
118 {
119 k=0;
120 for (j=0; j<N-1-i; j++)
121 {
122 if (Svertex[j].weight>Svertex[j+1].weight)
123 {
124 swap=Svertex[j]; //按权重由小到大的顺序对源顶点数组排序
125 Svertex[j]=Svertex[j+1];
126 Svertex[j+1]=swap;
127 k=1;
128 }
129 }
130 if (k==0)
131 break;
132 }
133
134 if (Svertex[N-2].weight==0)
135 k=-2;
136 else
137 {
138 k=-1;
139 while (Svertex[k+1].weight==0) //求源顶点数组中权重为零的节点的最大标号
140 {
141 k++;
142 }
143 }
144 }
145
146 if (k==-2)
147 {
148 printf("不存在顶点V%d到顶点V%d", m, 1); //源顶点和其余各顶点无边相连，问题无解
149 for (i=2; i<=N; i++)
150 {
151 if (i==m)
152 continue;
153 printf(",V%d", i);
154 }
155 printf("的最短路径,单源最短路径问题无解\n");
156 }
157 else //求源顶点到其余各顶点的最短路径
158 {
159 for (i=0; i<=k; i++)
160 {
161 spo=0;
162
163 for (j=k+1; j<N-1; j++)
164 {
165 if (r[m-1][Svertex[j].col]!=2)
166 continue;
167
168 z[m-1][Svertex[j].col]=z[Svertex[j].col][m-1]=1;
169 FindRoad(Svertex[j].col, Svertex[i].col, m, p, q, r, z, &spo, &head, &tail, Svertex[i].col, Svertex[j].col);
170 z[m-1][Svertex[j].col]=z[Svertex[j].col][m-1]=0;
171 }
172 SOutput(&spo, &head, &tail, Svertex[i].col, m, r, q); //输出最短路径及长度
173 }
174
175 printf("源点V%d到顶点V%d的最短路径长为%d\n", m, Svertex[i].col+1, q[m-1][Svertex[i].col]); //输出最短路径及长度
176 printf("源点V%d到顶点V%d的最短路径为:\n", m, Svertex[i].col+1);
177 printf("V%d->V%d\n", m, Svertex[i].col+1);
178
179 if (i<N-2)
180 z[Svertex[i].col][m-1]=z[m-1][Svertex[i].col]=0;
181 for (j=i+1; j<N-1; j++)
182 z[Svertex[j].col][m-1]=z[m-1][Svertex[j].col]=1;
183
184 for (i++; i<N-1; i++)
185 {
186 flag=0;
187 for (j=k+1; j<i-1; j++)
188 {
189 if (Svertex[j].mark!=2)
190 {
191 if (Svertex[j].mark==1)
192 {
193 if (Svertex[i-1].weight!=Svertex[i].weight)
194 {
195 Svertex[j].mark=2;
196 z[Svertex[j].col][m-1]=z[m-1][Svertex[j].col]=0;
197 flag=1;
198 }
199 }
200 }
201 else
202 {
203 flag=1;
204 }
205 }
206 if (r[m-1][Svertex[j].col]!=2)
207 {
208 Svertex[j].mark=0;
209 z[Svertex[j].col][m-1]=z[m-1][Svertex[j].col]=1;
210 }
211 else
212 {
213 if (Svertex[j].weight==Svertex[i].weight)
214 {
215 Svertex[j].mark=1;
216 z[Svertex[j].col][m-1]=z[m-1][Svertex[j].col]=1;
217 }
218 else
219 {
220 Svertex[j].mark=2;
221 flag=1;
222 }
223 }
224 spo=0;
225
226 if (flag==0)
227 {
228 printf("源点V%d到顶点V%d的最短路径长为%d\n", m, Svertex[i].col+1, q[m-1][Svertex[i].col]); //输出最短路径及长度
229 printf("源点V%d到顶点V%d的最短路径为:\n", m, Svertex[i].col+1);
230 printf("V%d->V%d\n", m, Svertex[i].col+1);
231 }
232 else
233 {
234 for (j=k+1; j<i; j++) //求源顶点到剩下各顶点的最短路径
235 {
236 if (Svertex[j].mark!=2)
237 continue;
238
239 z[m-1][Svertex[j].col]=z[Svertex[j].col][m-1]=1;
240 FindRoad(Svertex[j].col, Svertex[i].col, m, p, q, r, z, &spo, &head, &tail, Svertex[i].col, Svertex[j].col);
241 z[m-1][Svertex[j].col]=z[Svertex[j].col][m-1]=0;
242 }
243 z[m-1][Svertex[i].col]=z[Svertex[i].col][m-1]=0;
244 SOutput(&spo, &head, &tail, Svertex[i].col, m, r, q); //输出最短路径及其长度
245 }
246 }
247 }
248 }
249
250 void Fillr(int m, int p[][N], int q[][N], int r[][N], int z[][N], Order1 *Svertex, int *k)
251 {
252 int i, j, h, flag, mark, symbol, out;
253 Link1 *headm, *main, *minor, *psnewm;
254 Order1 swap;
255
256 headm=(Link1 *) malloc(sizeof(Link1));
257 headm->next=NULL;
258 main=headm;
259
260 for (i=0; i<N-1; i++)
261 {
262 if (i!=m-1)
263 {
264 for (j=0; j<N; j++)
265 {
266 if (j==i)
267 continue;
268 else
269 {
270 if (p[i][j]==0)
271 {
272 if (j>i)
273 r[i][j]=0;
274 continue;
275 }
276 else
277 {
278 psnewm=(Link1 *) malloc(sizeof(Link1)); //除源顶点外其他到源顶点权重不为零的顶点的标号和到源顶点权重存入Link1链表相应各节点
279 psnewm->col=j;
280 psnewm->weight=q[i][j];
281 insert(headm, psnewm);
282 }
283 }
284 }
285
286 if (headm->next!=NULL)
287 {
288 main=headm->next;
289 if (main->col>i)
290 *(r[i]+main->col)=2;
291
292 if (main->next!=NULL)
293 {
294 psnewm=main;
295 main=main->next;
296 int Node[N]={0}; //初始化Node数组,Node[i]==1表示i+1节点已被访问,==0表示未被访问
297 Node[i]=1; //源顶点已被访问
298 while(main!=NULL)
299 {
300 flag=1;
301 j=0;
302 if (r[i][psnewm->col]!=2)
303 z[i][psnewm->col]=1;
304 else
305 z[i][psnewm->col]=0;
306
307 if (psnewm->weight!=main->weight)
308 {
309 psnewm->mark=1;
310 j=1;
311
312 if (main->col>i)
313 {
314 mark=0;
315 if (z[i][psnewm->col]==0)
316 {
317 z[psnewm->col][i]=z[i][psnewm->col]=1;
318 mark=1;
319 }
320
321 h=Length(psnewm->col, main->col, q, z, Node); //求psnewm->col+1顶点到main->col+1顶点之最短路径
322
323 if (mark==1)
324 z[psnewm->col][i]=z[i][psnewm->col]=0;
325
326 if (h!=0)
327 {
328 if (h+psnewm->weight<main->weight)
329 {
330 r[i][main->col]=1; //连接i+1顶点和main->col+1的边不是最短路径
331 flag=0;
332 }
333 }
334 }
335 }
336 else
337 {
338 psnewm->mark=0;
339 }
340
341 minor=headm->next;
342 while (minor!=psnewm)
343 {
344 if (minor->mark==1||minor->mark==0&&psnewm->weight!=main->weight)
345 {
346 if (minor->mark==0&&psnewm->weight!=main->weight)
347 minor->mark=1;
348 j=1;
349
350 if (flag!=0&&main->col>i)
351 {
352 mark=0;
353 if (z[i][minor->col]==0)
354 {
355 z[minor->col][i]=z[i][minor->col]=1;
356 mark=1;
357 }
358
359 h=Length(minor->col, main->col, q, z, Node); //求minor->col+1顶点到main->col+1顶点之最短路径
360
361 if (mark==1)
362 z[minor->col][i]=z[i][minor->col]=0;
363
364 if (h!=0) /*注意这里*/
365 {
366 if (h+minor->weight<main->weight)
367 {
368 r[i][main->col]=1; //连接i+1顶点和main->col+1的边不是最短路径
369 flag=0;
370 }
371 }
372 }
373 }
374 minor=minor->next;
375 }
376
377 if (main->col>i)
378 {
379 if (j==0)
380 r[i][main->col]=2; //连接i+1顶点和main->col+1的边是最短路径
381 else
382 {
383 if (flag==1)
384 r[i][main->col]=2; //连接i+1顶点和main->col+1的边是最短路径
385 }
386 }
387
388 psnewm=psnewm->next;
389 main=main->next;
390 }
391
392 for (j=0; j<N; j++)
393 {
394 if (j==i)
395 continue;
396 z[i][j]=0; //将z矩阵i+1行清零
397 }
398
399 main=headm;
400 while (main->next!=NULL)
401 {
402 psnewm=main->next;
403 main->next=psnewm->next;
404 free(psnewm);
405 } /*外层循环结束后Link1型链表释放完毕*/
406 }
407 }
408 for (j=i+1; j<N; j++)
409 r[j][i]=r[i][j]; //填充r矩阵对称与对角线的另一列
410 }
411 else
412 {
413 h=0;
414 for (j=0; j<N; j++)
415 {
416 if (j!=i)
417 {
418 Svertex[h].col=j;
419 Svertex[h].weight=q[i][j]; //将除源顶点外其他顶点的标号和他们到源顶点权重存入源顶点结构体数组相应各节点
420 h++;
421 }
422 }
423
424 for (j=1; j<N-1; j++)
425 {
426 flag=0;
427 for (h=0; h<N-1-j; h++)
428 {
429 if (Svertex[h].weight>Svertex[h+1].weight) //按权重从小到大顺序对源顶点数组执行排序
430 {
431 swap=Svertex[h];
432 Svertex[h]=Svertex[h+1];
433 Svertex[h+1]=swap;
434 flag=1;
435 }
436 }
437 if (flag==0)
438 break;
439 }
440
441 if (Svertex[N-2].weight==0) //源顶点数组各节点权重均为零
442 {
443 *k=-2;
444 for (j=N-1; j>i; j--)
445 r[i][j]=0;
446 }
447 else
448 {
449 out=-1;
450 while (Svertex[out+1].weight==0)
451 {
452 out++; //求源顶点数组中权重为零的节点的最大标号
453 if (Svertex[out].col>i)
454 r[i][Svertex[out].col]=0;
455 }
456 *k=out;
457
458 r[i][Svertex[++out].col]=2; //以下部分和i!=m-1时的情况类似
459 int Node[N]={0};
460 Node[i]=1;
461 for (out++; out<N-1; out++)
462 {
463 flag=1;
464 j=0;
465 if (r[i][Svertex[out-1].col]!=2)
466 z[i][Svertex[out-1].col]=1;
467 else
468 z[i][Svertex[out-1].col]=0;
469
470 if (Svertex[out-1].weight!=Svertex[out].weight)
471 {
472 Svertex[out-1].mark=1;
473 j=1;
474
475 if (Svertex[out].col>i)
476 {
477 mark=0;
478 if (z[i][Svertex[out-1].col]==0)
479 {
480 z[Svertex[out-1].col][i]=z[i][Svertex[out-1].col]=1;
481 mark=1;
482 }
483
484 h=Length(Svertex[out-1].col, Svertex[out].col, q, z, Node);
485
486 if (mark==1)
487 z[Svertex[out-1].col][i]=z[i][Svertex[out-1].col]=0;
488
489 if (h!=0) /*注意这里*/
490 {
491 if (h+Svertex[out-1].weight<Svertex[out].weight)
492 {
493 r[i][Svertex[out].col]=1;
494 flag=0;
495 }
496 }
497 }
498 }
499 else
500 {
501 Svertex[out-1].mark=0;
502 }
503
504 for (symbol=*k+1; symbol<out-1; symbol++)
505 {
506 if (Svertex[symbol].mark==1||Svertex[symbol].mark==0&&Svertex[out-1].weight!=Svertex[out].weight)
507 {
508 if (Svertex[symbol].mark==0&&Svertex[out-1].weight!=Svertex[out].weight)
509 Svertex[symbol].mark=1;
510 j=1;
511
512 if (flag!=0&&Svertex[out].col>i)
513 {
514 mark=0;
515 if (z[i][Svertex[symbol].col]==0)
516 {
517 z[Svertex[symbol].col][i]=z[i][Svertex[symbol].col]=1;
518 mark=1;
519 }
520
521 h=Length(Svertex[symbol].col, Svertex[out].col, q, z, Node);
522
523 if (mark==1)
524 z[Svertex[symbol].col][i]=z[i][Svertex[symbol].col]=0;
525
526 if (h!=0) /*注意这里*/
527 {
528 if (h+Svertex[symbol].weight<Svertex[out].weight)
529 {
530 r[i][Svertex[out].col]=1;
531 flag=0;
532 }
533 }
534 }
535 }
536 }
537
538 if (Svertex[out].col>i)
539 {
540 if (j==0)
541 r[i][Svertex[out].col]=2;
542 else
543 {
544 if (flag==1)
545 r[i][Svertex[out].col]=2;
546 }
547 }
548 }
549 for (j=0; j<N; j++)
550 {
551 if (j==i)
552 continue;
553 z[i][j]=0;
554 }
555 }
556 for (j=i+1; j<N; j++)
557 r[j][i]=r[i][j];
558 }
559 }
560 free(headm);
561 }
562
563 int Length(int start, int end, int q[][N], int z[][N], int Node[])
564 {
565 int i;
566 int L, S; //L用于保存start到end的最短路径长度
567 L=0; //L初始化
568
569 Node[start]=1; //start标记为已访问
570 for (i=0; i<N; i++)
571 {
572 if (i==start) //下一个要访问的节点不能是start
573 continue;
574
575 if (z[start][i]==0&&q[start][i]!=0&&Node[i]==0) //i作为下一个要访问的顶点合法
576 {
577 if (i==end) //抵达终点
578 {
579 if (L==0)
580 L=q[start][i];
581 else
582 {
583 if (q[start][i]<L) //比较大小，求最短路径长
584 L=q[start][i];
585 }
586 }
587 else //未到终点
588 {
589 z[start][i]=z[i][start]=1;
590
591 if ((S=Length(i, end, q, z, Node))!=0) //存在i到end的最短路径
592 {
593 if (L==0)
594 L=q[start][i]+S;
595 else
596 {
597 if (q[start][i]+S<L) //比较大小，求最短路径长
598 L=q[start][i]+S;
599 }
600 }
601
602 z[start][i]=z[i][start]=0;
603 }
604 }
605 }
606 Node[start]=0; //还原start访问状态
607 return L; //返回最短路径长度
608 }
609
610 void insert(Link1 *headm, Link1 *psnewm)
611 {
612 Link1 *mainaf, *mainbe;
613
614 if (headm->next==NULL)
615 {
616 psnewm->next=NULL;
617 headm->next=psnewm;
618 }
619 else
620 {
621 mainbe=headm;
622 mainaf=headm->next;
623 while (mainaf!=NULL)
624 {
625 if (psnewm->weight<=mainaf->weight)
626 {
627 psnewm->next=mainaf;
628 mainbe->next=psnewm;
629 return;
630 }
631 mainbe=mainbe->next;
632 mainaf=mainaf->next;
633 }
634 psnewm->next=NULL;
635 mainbe->next=psnewm;
636 }
637 }
638
639 int Enable(int i, int j, int p[][N], int r[][N], int z[][N], int node[])
640 {
641 if (p[i][j]==0)
642 return 0;
643 else
644 {
645 if (r[i][j]!=2)
646 return 0;
647 else
648 {
649 if (node[j]==1)
650 {
651 return 0;
652 }
653 else
654 {
655 if (z[i][j]==1)
656 return 0;
657 else
658 return 1;
659 }
660 }
661 }
662 }
663
664 int Search(int k, int option, int p[][N], int r[][N], int z[][N], int node[])
665 {
666 int m=option;
667
668 for (m++; m<N; m++) //搜索option顶点后的第一个可达顶点
669 {
670 if (Enable(k, m, p, r, z, node)==1)
671 return m; //搜索成功，返回
672 }
673 return -1; //搜索失败
674 }
675
676 void FindRoad(int start, int end, int m, int p[][N], int q[][N], int r[][N], int z[][N], int *spo, Shortest1 **heads, Shortest1 **tail, int k1, int p1)
677 {
678 int i, k; //i为当前顶点,k为当前节点的下一可达节点
679 int interval;
680 int RoadLength; //搜索到的路径长度
681 int node[N]={0}; //初始化顶点访问数组Node
682
683 Path1 *psnewbe, *psnewaf, *head, *current;
684 head=(Path1 *) malloc(sizeof(Path1));
685 psnewbe=head;
686 psnewaf=head; //初始化路径链表
687 head->pnext=NULL;
688 head->pbefore=NULL;
689
690 node[m-1]=1; //m标记为已访问
691 node[start]=1; //start标记为已访问
692 i=start; k=-1; //初始化i,k
693 while (1)
694 {
695 if (Search(i, k, p, r, z, node)==-1) //搜索从k起的下一个可达顶点失败
696 {
697 if (i==start) //路径搜索完毕，退出
698 break;
699 else
700 {
701 if (k==-1)
702 {
703 z[psnewaf->sign][i]=z[i][psnewaf->sign]=0;
704 node[i]=0;
705 i=psnewaf->sign; //回溯
706 k=psnewaf->next;
707 continue;
708 }
709 else
710 {
711 z[psnewbe->sign][i]=z[i][psnewbe->sign]=0;
712 node[i]=0;
713 RoadLength-=q[psnewbe->sign][i];
714 free (psnewaf);
715 psnewbe->pnext=NULL; //回溯
716 psnewaf=psnewbe;
717 psnewbe=psnewbe->pbefore;
718 i=psnewaf->sign;
719 k=psnewaf->next;
720 continue;
721 }
722 }
723 }
724 else //搜索出下一可达顶点
725 {
726 if (k==-1)
727 {
728 current=(Path1 *) malloc(sizeof(Path1));
729 current->sign=i; //建立表示当前顶点i的路径节点
730 current->next=interval=Search(i, k, p, r, z, node);
731 if (i==start)
732 RoadLength=0;
733 else
734 {
735 RoadLength+=q[psnewaf->sign][i]; //更新路径长度
736 }
737 z[current->next][i]=z[i][current->next]=1; //连接i和下一可达顶点的边标记为已访问
738 node[current->next]=1; //下一可达顶点标记为已访问
739 current->pnext=NULL;
740 psnewaf->pnext=current;
741 current->pbefore=psnewaf; //当前节点插入路径链表
742 psnewbe=psnewaf;
743 psnewaf=current;
744 }
745 else
746 {
747 psnewaf->next=interval=Search(i, k, p, r, z, node); //更新下一可达节点标号
748 z[psnewaf->next][i]=z[i][psnewaf->next]=1; //连接i和下一可达顶点的边标记为已访问
749 node[psnewaf->next]=1; //下一可达顶点标记为已访问
750 }
751
752 i=interval; //更新i为下一可达顶点
753 k=-1; //k重置
754
755 if (i==end) //到达终点
756 {
757 current=(Path1 *) malloc(sizeof(Path1));
758 current->sign=i; //建立表示终点的路径节点即路径链表尾节点
759 RoadLength+=q[psnewaf->sign][i]; //更新路径长度
760 current->pnext=NULL;
761 psnewaf->pnext=current; //尾节点插入路径链表
762 current->pbefore=psnewaf;
763
764 SOperate(spo, heads, tail, k1, m, r, q, RoadLength, head, p1);/*根据找到的新路径调用SOperate函数筛选路径*/
765
766 free (current); //删除尾节点
767 psnewaf->pnext=NULL;
768 RoadLength-=q[psnewaf->sign][i];
769 z[psnewaf->sign][i]=z[i][psnewaf->sign]=0; //回溯
770 node[i]=0;
771
772 i=psnewaf->sign;
773 k=psnewaf->next;
774 }
775 continue;
776 }
777 }
778 if (head->pnext!=NULL)
779 free(psnewaf); //完全删除路径链表
780 free(head);
781 }
782
783 Shortest1 *Copy(Path1 *headp)
784 {
785 Shortest1 *head;
786 assist1 *tail, *psnew;
787 Path1 *visit;
788
789 head=(Shortest1 *) malloc(sizeof(Shortest1)); //建立指向找到的新路径的头节点
790 head->pbe=NULL;
791 head->passist=NULL; //头节点始化
792 visit=headp->pnext; //visit指向路径链表第一个节点
793
794 while (visit!=NULL) //遍历路径链表
795 {
796 psnew=(assist1 *) malloc(sizeof(assist1));
797 psnew->tab=visit->sign; //拷贝路径节点代表的顶点标号至assist1节点
798 psnew->next=NULL;
799 if (head->passist==NULL)
800 {
801 head->passist=psnew;
802 tail=psnew; //assist1节点插入头节点指向的路径
803 }
804 else
805 {
806 tail->next=psnew;
807 tail=psnew;
808 }
809 visit=visit->pnext;
810 }
811
812 return (head); //返回指向指向找到的新路径的头节点的指针
813 }
814
815 void Delete(Shortest1 **heads, Shortest1 **tail)
816 {
817 Shortest1 *row; //用来指向待删除的指向搜索出的路径的节点的指针
818 assist1 *col; //用来指向待删除的路径节点
819 *tail=*heads;
820
821 while ((*tail)->pbe!=NULL)
822 {
823 row=(*tail)->pbe;
824 (*tail)->pbe=row->pbe;
825 while (row->passist!=NULL) //逐一删除所有路径以及指向路径的Shortest1节点
826 {
827 col=row->passist;
828 row->passist=col->next;
829 free(col);
830 }
831 free(row);
832 }
833 }
834
835 void SOperate(int *spo, Shortest1 **heads, Shortest1 **tail, int k, int m, int r[][N], int q[][N], int RoadLength, Path1 *headp, int p)
836 {
837 if (r[m-1][k]!=2) //连接m-1和k的边不是最短路径
838 {
839 if (r[m-1][k]==1) //m-1和k有边相连
840 {
841 if (RoadLength+q[m-1][p]>=q[m-1][k]) //m到p+1到k+1的路径不是m到k+1的最短路径
842 return;
843 }
844 Shortest1 *carbon;
845 //m到p+1到k+1的路径有可能是m到k+1的最短路径
846 if ((*heads)->pbe==NULL)
847 {
848 *spo=RoadLength+q[m-1][p];
849 carbon=Copy(headp); //Shortest1链表为空,直接将找到的路径插入
850 (*heads)->pbe=carbon;
851 *tail=carbon;
852 }
853 else
854 {
855 if (*spo<RoadLength+q[m-1][p])
856 return;
857 else
858 {
859 if (*spo==RoadLength+q[m-1][p])
860 {
861 carbon=Copy(headp);
862 (*tail)->pbe=carbon; //将找到的路径插入Shortest1链表
863 *tail=carbon;
864 }
865 else
866 {
867 Delete(heads, tail); //删除Shortest1链表和所有路径(Shortest1链表头节点不删除)
868 *spo=RoadLength+q[m-1][p];
869 carbon=Copy(headp);
870 (*heads)->pbe=carbon; //Shortest1链表为空,直接将找到的路径插入
871 *tail=carbon;
872 }
873 }
874 }
875 }
876 else
877 {
878 if (RoadLength+q[m-1][p]==q[m-1][k]) //m到p+1到k+1的路径是m到k+1的最短路径
879 {
880 Shortest1 *carbon;
881 carbon=Copy(headp); //将找到的路径插入Shortest1链表
882 (*tail)->pbe=carbon;
883 *tail=carbon;
884 }
885 else
886 {
887 return; //m到p+1到k+1的路径不是m到k+1的最短路径，返回
888 }
889 }
890 }
891
892 void SOutput(int *spo, Shortest1 **heads, Shortest1 **tail, int k, int m, int r[][N], int q[][N])
893 {
894 if ((*heads)->pbe==NULL) //Shortest1链表为空
895 {
896 if (r[m-1][k]==0)
897 printf("源点V%d和顶点V%d间不存在最短路径,即不连通\n", m, k+1);
898 else
899 {
900 printf("源点V%d到顶点V%d的最短路径长为%d\n", m, k+1, q[m-1][k]); //连接m和k+1的边即为m到k+1的唯一最短路径
901 printf("源点V%d到顶点V%d的最短路径为:\n", m, k+1);
902 printf("V%d->V%d\n", m, k+1);
903 }
904 }
905 else
906 {
907 Shortest1 *row;
908 assist1 *col;
909 if (r[m-1][k]==2)
910 printf("源点V%d到顶点V%d的最短路径长为%d\n", m, k+1, q[m-1][k]);
911 else
912 printf("源点V%d到顶点V%d的最短路径长为%d\n", m, k+1, *spo);
913
914 printf("源点V%d到顶点V%d的最短路径为:\n", m, k+1);
915
916 if (r[m-1][k]==2)
917 printf("V%d->V%d\n", m, k+1);
918
919 *tail=*heads;
920 while ((*tail)->pbe!=NULL)
921 {
922 row=(*tail)->pbe;
923 (*tail)->pbe=row->pbe;
924 printf("V%d", m);
925 while (row->passist!=NULL) //逐一输出找到的m到k+1的最短路径,同时删除所有路径清空Shortest1链表
926 {
927 col=row->passist;
928 row->passist=col->next;
929 printf("->V%d", col->tab+1);
930 free(col);
931 }
932 printf("\n");
933 free(row);
934 }
935 }
936 }
对于如下的单边无向无环非负权重的图
Vi i=1,2,3,4,5,6,7表示图的顶点,数字表示各边的权重，则图的邻接矩阵为
权重矩阵为
在程序中输入以上邻接矩阵和权重矩阵，单源最短路径的源顶点输入为V1，则程序运行结果如下图：
可以验证这是正确的
上一篇： JSP设置文件编码
下一篇： WebSocket就是这么简单