【正文】 [j]=MAXNUM。 } } 重慶科技學(xué)院 本科生課程設(shè)計 附錄 17 ifstream weight_file(,ios::in)。//從 中讀入權(quán)重的值 if(!weight_file)exit(1)。 for(k=0。k。k++)//講權(quán)值帶入矩陣當中 { weight_fileijw。 [i][j]=w。 [j][i]=[i][j]。 } } void DisIntroduction(MGraph G)//提供景點的信息 { char n1[20]。 int v1。 cout請輸入所要查詢的景點的名稱 :endl。 cinn1。 int count1=0。 for(int i=0。i。i++) { int m = strcmp([i].name,n1)。 if(m==0) { v1=i。 count1=count1+1。 } } if(count1!=1) { cout您輸入的名稱有誤 !endl。 cout請選擇要進行的操作 (I:查詢景點信息， P:查詢兩個景點之間的最短路徑， Q:退出 )endl。 } else { cout該景點的簡介為 :39。\t39。[v1].introductionendl。 cout請選擇要進行的操作 (I:查詢景點信息， P:查詢兩個 景點之間的最短路徑， Q:退出 )endl。 } } void DisPath(MGraph G)//查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑 重慶科技學(xué)院 本科生課程設(shè)計 附錄 18 { int v1,v2。 char n1[20],n2[20]。 cout請輸入要查詢的最短路徑的兩個頂點名稱 :endl。 cinn1n2。 int count=0。 for(int i=0。i。i++) { int m1= strcmp([i].name,n1)。 int m2= strcmp([i].name,n2)。 if(m1==0) { v1=i。 count++。 } else if(m2==0) { v2=i。 count++。 } } if(count!=2) { cout您輸入的名稱有誤 !endl。 cout請選擇要進行的操作 (I:查詢景點信息， P:查詢兩個景點之間的最短路徑， Q:退出 )endl。 } ShortPath_DIJ(G,v1,v2)。 } void Exit() //退出 { cout歡迎下次繼續(xù)使用 !endl。 exit(0)。 } include include include include include include 重慶科技學(xué)院 本科生課程設(shè)計 附錄 19 define MAX_VERTEX_NUM 10 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 typedef struct Vertex//定義圖中頂點的數(shù)據(jù)類型 { int num。 char name[14]。 char introduction[100]。 }Vertex。 typedef struct //定義圖的數(shù)據(jù)類型 { Vertex vexs[MAX_VERTEX_NUM]。 AdjMatrix arcs。 int vexnum,arum。 }MGraph。 void CreateUDN(MGraph amp。G)。 void ShortPath_DIJ(MGraph G,int v0,int v2)。 void DisIntroduction(MGraph G)。 void DisPath(MGraph G)。 void Exit()。 includeiostream includefstream includecstring define MAXNUM 10000 define TRUE 1 define FALSE 0 using namespace std。 void ShortPath_DIJ(MGraph G,int v0,int v2)//Dijkstra 算法求最短路徑 //Path[w]表示從 v0到 w的最短路徑； D[w]表示從 v0到 w的最短距離 { int v,w,i,j,m。 int Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 int D[MAX_VERTEX_NUM]。 int final[MAX_VERTEX_NUM]。 for(v=0。v。v++)//各對節(jié)點之間初始已知路徑及距離 { 重慶科技學(xué)院 本科生課程設(shè)計 附錄 20 final[v]=FALSE。 D[v]=[v0][v]。 for(w=0。w。w++) { P[v][w]=FALSE。 } if(D[v]MAXNUM) { P[v][v0]=TRUE。 P[v][v]=TRUE。 } } D[v0]=0。 final[v0]=TRUE。 int a[20]。 for(i=0。i。i++)//對 Path[i][j]進行初始化，使其值全部為 1000，便于后期的判斷 { for(j=0。j。j++) { Path[i][j]=1000。 } } for(i=0。i。i++)//對數(shù)組進行初始化，以便對 Path[i][j]進行描述 { a[i]=1。 } for(v=0。v。v++)//各條路線的初始節(jié)點為 v0 { Path[v][0]=v0。 } //開始主循環(huán)，每次求解得到 v0 到某個 v 頂點的最短路徑，并加入到 S 集合中 for(i=1。i。i++) { m=MAXNUM。//當前所知的離 v0 最近的距離 for(w=0。w。w++) { if(!final[w])//w 頂點在 VS中 { if(D[w]m) { v=w。 重慶科技學(xué)院 本科生課程設(shè)計 附錄 21 m=D[w]。 } } } Path[v][a[v]]=v。 final[v]=TRUE。 for(w=0。w。w++) { if((!final[w])amp。amp。(m+[v][w]D[w])) { D[w]=m+[v][w]。//修改當前的最短路徑的值 int k0=1。 a[w]=1。 while(Path[v][k0]!=1000) //如果上述條件成立， Path[w]路徑需要改變，因為從 v0到w的路徑顯然經(jīng)過了 v0 和 v 之間的所有的點（包括 v） { Path[w][k0]=Path[v][k0]。 k0++。 a[w]++。 } } } } cout兩個景點之間的最短路徑為 :39。\t39。 int k=0。 while(Path[v2][k]!=1000) { int m=Path[v2][k]。 cout[m].name39。\t39。 k++。 } coutendl。 cout兩個景點之間的最短距離為 : D[v2]Mendl。 cout請選擇要進行的 操作 (I:查詢景點信息， P:查詢兩個景點之間的最短路徑， Q:退出 )endl。 }