单源最短路径

  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 }