【正文】 printf(\n)。 } else if(j!=m) printf(\n%c到%c : no path,gvexs[j],gvexs[m])。}void Dijkstra_Two(ALGraph *G, MGraph *g,char v0,char d,int distance[], int pre[]){ // 帶權圖G從頂點v0到其他定點的最短距離distance和最短路徑前驅結點的下標pre int w,m,n。 int S[30],i,j,k,p,min。 //char d。 m=LocateVexx(G, v0) 。 //printf(你所要開始查詢的開始景點是:%c\n\n,GAdjList[v0].data)。 for(i=0。igvexnum。i++) /* 各數(shù)組的初始化 */ { distance[i]=gadj[m][i]。 S[i]=0。 if(distance[i]INFINITY) pre[i]=m。 else pre[i]=1。 } S[m]=1。 //頂點v0已加入到集合S中 設置s={v0} for(i=0。igvexnum。i++)// 找不在S中的頂點vk { min=INFINITY。 for(j=0。jgvexnum。j++) { if(!S[j]amp。amp。distance[j]min) { min=distance[j]。 k=j。 } } /* 求出當前最小的distance[j]值 */ S[k]=1。 //將找到的頂點加入到集合S中 for(w=0。wgvexnum。w++) // 修改集合s中頂點的距離值 if(!S[w]amp。amp。distance[w]distance[k]+gadj[k][w]) { distance[w]=distance[k]+gadj[k][w]。 pre[w]=k。 }//修改distance和pre數(shù)組的值 } //printf(輸入你要查詢的另外一個景點(下標值):)。 //scanf(%c,amp。d)。 n=LocateVexx(G, d)。 //printf(你要查詢的另外一個景點是:%c\n,gvexs[n])。 printf(\n查詢結果:\n)。 //輸出結果 if(pre[n]!=1) { printf(從景點%c到景點%c,GAdjList[m].data,gvexs[n])。 p=pre[n]。 printf(的最短距離是: %d,distance[n])。 printf( 途中經(jīng)過的景點有:)。 while(p!=1) { printf( %c,gvexs[p])。 p=pre[p]。 } printf(\n)。 }}void dfs_path(ALGraph *g,int src,int cur,int vis[],GPath *cur_path,GPath * min_path){ if(vis[src]) { if(cur_pathcount==gvexnum) { if(cur_pathvaluemin_pathvalue) { memcpy(min_path,cur_path,sizeof(GPath))。/*由cur_path所指內(nèi)存區(qū)域復制sizeof(GPath)個字節(jié)到min_path所指內(nèi)存區(qū)域*/ return。 } } return。 } ArcNode * node =gAdjList[cur].firstarc。 for(。node!=NULL。 node=nodenextarc)/*起始條件為node =gAdjList[cur].firstarc*/ { char adj=nodeadjvex。 int index=LocateVexx(g,adj)。 if(vis[index]==0) { cur_pathvertex[cur_pathcount++]=index。 cur_pathvalue+=nodeinfo。 vis[index]=1。 dfs_path(g,src,index,vis,cur_path,min_path)。 cur_pathcount。 cur_pathvalue=nodeinfo。 vis[index]=0。 } }}void best_path(ALGraph *g,int src){ int vis[MAXVEX]。 memset(vis,0,sizeof(vis))。 GPath cur_path,min_path。 memset(amp。cur_path,0,sizeof(GPath))。/*將cur_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向cur_path的指針。*/ memset(amp。min_path,0,sizeof(GPath))。/*將min_path所指向的某一塊內(nèi)存中的每個字節(jié)的內(nèi)容全部設置為0指定的ASCII值, 塊的大小由第三個參數(shù)指定,這個函數(shù)通常為新申請的內(nèi)存做初始化工作, 其返回值為指向min_path的指針。*/ =INFINITY。 dfs_path(g,src,src,vis,amp。cur_path,amp。min_path)。 if(!=INFINITY) { int i=0。 printf(\n最佳旅游路線景點下標值是:\n)。 for(i=0。 i。 i++) { printf(%d ,[i])。 } printf(\n)。 printf(\n最佳旅游路線景點是:\n)。 for(i=0。 i。 i++) { printf(%c ,gAdjList[[i]].data)。 } printf(\n)。 }else { printf(建立的圖中沒有最佳路徑\n)。 }}void main(){ int m。 int n, opse。 char vp,v0,d,src。 int distance[MAXVEX],pre[2*MAXVEX]。 ALGraph *G。 MGraph *M。 do { printf(\n\n請選擇對圖的操作要求:\n\n)。 for (n=0。 n=5。 n++) printf(* )。 printf(\n* )。 printf(1建立圖的鄰接矩陣 )。 printf( 2圖的鄰接矩陣的輸出 )。 printf( *\n)。 printf(\n* )。 printf(3圖的鄰接鏈表的輸出 )。 printf( 4相鄰景點查詢(下標值) )。 printf( *\n)。 printf(\n* )。 printf(5 從某點出發(fā)到另外所有點最短簡單路徑及距離(下標值) )。 printf( *\n)。 printf(\n* )。 printf(6 兩個景點之間的最短距離(下標值) )。 printf( *\n)。 printf(\n* )。 printf(7 最佳路徑 )。 printf(8 退出 )。 printf( *\n)。 for (n=0。 n=5。 n++) printf(* )。 printf(\n\n)。 do { scanf(%d,amp。opse)。 }while (opse1||opse8)。 switch (opse) { case 1: { M=(MGraph *)malloc(sizeof(MGraph)) 。 M=create_graph() 。 printf(\n\n)。 break 。 } case 2: { printf(\n您所建立的圖是：\n) 。 output_graphic(M) 。 break 。 } case 3: { printf( 圖G的鄰接矩陣轉換成鄰接表:\n)。 G = MGraphToALGraph(M,G)。 output_graphic_c(M,G)。 break 。 } case 4: { printf(\n請輸入你要查詢的景點：\n) 。 scanf( %c,amp。vp)。 output_Find_ALGraph(G,vp)。 break 。 } case 5: { printf(\n輸入一個頂點是：\n) 。 scanf( %c,amp。v0)。 Dijkstra_One(G,M,v0,distance,pre)。 break 。 } case 6: { printf(你所要開始查詢的開始景點是:\n\n)。 scanf( %c,amp。v0)。 printf(你要查詢的另外一個景點是:\n)。 scanf( %c,amp。d)。 Dijkstra_Two(G,M,v0,d,distance,pre)。 break。 } case 7: { printf(輸入你要查詢的開始景點:)。 scanf( %c,amp。v0)。 m=LocateVexx(G, v0) 。 best_path(G,m)。 break。 } } } while(opse!=8)。}6 問題與總結問題：第一次答辯的時候，老師要求景點名稱在后面也要輸入字符型，回來后，想了一下，用了一個簡單的辦法，即調(diào)用LocateVexx函數(shù)返回我輸入景點所對應的下標值。這樣就避免了只能輸入下標值帶來的不便了；沒有完全符合最后一題的意思完成該題，最后一小題題目要求是可以重復經(jīng)過某些點，但是我的程序是每個點只經(jīng)過一次的最短回路（即所建的圖需是哈密頓圖才有回路，否則會輸出沒有最短路徑）；為了解決這個問題，我在網(wǎng)上也看了很多的資料，比如：TSP問題（旅行商問題/貨郎擔問題）、蟻群算法、模擬退火算法、KM算法、中國郵遞員算法等，其中發(fā)現(xiàn)經(jīng)典的旅行商問題（貨郎擔問題）并不符合題目最后一題的要求，下面是在網(wǎng)上截圖的資料：為了解決這個難題，雖然在網(wǎng)上找了很多的資料，努力了三天，但是還是沒有能力解決這個問題?？偨Y：將鄰接矩陣轉換為鄰接鏈表走了很多彎路、花了很長的時間；還有就是引用一些書上的函數(shù)時，要正確用函數(shù)對結構體成員調(diào)用，不能照搬過來，得看一下結構上的區(qū)別。