如果不瞭解單源最短路徑問題可以自行百度或參考演算法書籍，這裡只給出一種解法，對問題本身不做詳細介紹 在以下求解單源最短路徑問題的代碼中使用了重要的核心函數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=
