【正文】 s[i][j].adj=INFINITY。 Garcs[i][j].info=NULL。 } for(k=0。kGarum。k++) {//輸入各弧并構造鄰接矩陣 printf(請輸入邊的起點和終點和權值如（v1,v2,n）:)。//起始點和終點和兩點之間對應的權值 fflush(stdin)。 scanf(%c,%c,%d,amp。v1,amp。v2,amp。n)。 printf(\n)。 i=LocateVex(G,v1)。//確定v1的位置 j=LocateVex(G,v2)。//確定v2的位置 Garcs[i][j].adj=n。//邊v1,v2的權值賦為1，如需要權值操作則相應修改一下即可 Garcs[i][j].info=NULL。//如需要有相關信息則相對應輸入，在這里我設置為空 }//第二個forgetchar()。} //Creat_YGvoid juzhen(MGrph *G){//用矩陣來存儲并顯示出結果 int i,j,k。 printf(鄰接矩陣顯示：\n)。 printf(\t)。 for(i=0。iGvexnum。i++) printf(\t%5c,Gvexs[i])。 for(j=0。jGvexnum。j++) { printf(\n\n)。 printf(\t\%5c,Gvexs[j])。 for(k=0。kGvexnum。k++) { if(Garcs[j][k].adjINFINITY) printf(\t%5d,Garcs[j][k].adj)。 else printf(\t 3000)。 //無權值的直接輸出最大值 } }}void Short(MGrph *G,int path[],int i,int w){ //遞歸函數(shù)是用來輸出從源點出發(fā)到終點之前的頂點 //思想是patn[]數(shù)組來表示前驅頂點的位置，然后遞歸輸出每個頂點的前驅 int k。 k=path[i]。 if(k!=w) Short(G,path,k,w )。 printf(%c,Gvexs[k])。//輸出k位置的頂點值 }void ShortestPath(MGrph *G,int w){ //Dijkstrs算法應用 int i,k,m,n,min。 int final[30],path[30],D[30]。 //定義三個數(shù)組，final[]標記該頂點是否在最短路徑上 //path[]用來記錄頂點的前驅頂點的位置，D[]是用來記錄從源點到該點的最短路徑長度 for(i=0。iGvexnum。i++) { path[i]=w。//首先把所有頂點的前驅頂點的位置賦值為w位置，也就是源點的位置 final[i]=0。//這是一個標記數(shù)組，一開始所有頂點位置對應的數(shù)組值全部標記為0 D[i]=Garcs[w][i].adj。//D[]是用來記錄最短路徑的長度，一開始把所有頂點到源點的的距離賦值給它 } D[w]=0。final[w]=1。path[w]=100。//源點位置的D[w]為0，final[w]=1標記已經入集合，path[w]=100，表示該前驅為100 for(m=1。mGvexnum。m++) { min=INFINITY。//首先賦值為機內最大值 for(k=0。kGvexnum。k++) { if(!final[k]) if(D[k]min) { i=k。 min=D[k]。//最短路徑長度 } } final[i]=1。 for(n=0。nGvexnum。n++) if(!final[n]amp。amp。(min+Garcs[i][n].adj)D[n]) { D[n]=min+Garcs[i][n].adj。 path[n]=i。 }//if } //for for(m=0。mGvexnum。m++){ if(final[m]==1amp。amp。m!=w) {printf(\t從%c到%c的最短路徑長度為：%d\t路徑是：,Gvexs[w],Gvexs[m],D[m])。//輸出最大值時則表示兩點之間沒有最短路徑 Short(G,path,m,w)。 printf(%c,Gvexs[m])。 printf(\n)。 } else printf(\t從%c到%c沒有不存在路徑！\n,Gvexs[w],Gvexs[m])。//判斷是否存在最短路徑 } } main(){ MGrph m。 VertexType ch。 int j。 Creat_YG(amp。m)。 juzhen(amp。m)。 printf(\n請輸入要開始的頂點:)。 scanf(%c,amp。ch)。 j=LocateVex(amp。m,ch)。 getchar()。 ShortestPath(amp。m,j)。 getchar()。 }17