尋路算法實作

實作任意兩點間的尋路，自動選擇最優或較優路徑

1．基本要求

可以以矩陣表示地圖，

{1,1,1,1,1,1,1,1,1,1,1 }

{1,0,1,0,1,0,0,0,0,0,1 }

{1,0,1,0,0,0,1,0,1,1,1 }

{1,0,0,0,1,0,1,0,0,0,1 }

{1,0,1,1,0,0,1,0,0,1,1 }           0代表可以通過，1代表不可通過

{1,0,1,0,1,1,0,1,0,0,1 }

{1,0,0,0,0,0,0,0,1,0,1 }

{1,0,1,0,1,0,1,0,1,0,1 }

{1,0,0,1,0,0,1,0,1,0,1 }

{1,1,1,1,1,1,1,1,1,1,1 }

可以任意設定起點和終點，可以任意設定地圖，輸出路徑和步數。

2．項目擴充

在實作基本要求的情況下，進一步完善程式

可以加入移動力、地形以及移動在不同地形上的損耗等因素

可以用圖形化界面取代字元界面

用Dijkstra算法，我做的給你個參考，下面各點是有距離的（移動力），BIG表示不可通過

#define BIG 32767 //無窮大 

int pre[6]={0}; //這是關鍵！pre數組用于記錄每個點的前趨，這樣算出最短路徑後，就可以遞歸出路徑經過的點 

int Distance[6]; //用于記錄從起點到達每個點的最短路徑長度 

int Cost[6][6]={{0,1450,1650,BIG,BIG,BIG}, //有向網的鄰接矩陣，這裡以6個點為例 

　　　　　　　　{1450,0,BIG,1350,2350,BIG}, 

　　　　　　　　{1650,BIG,0,BIG,2550,BIG}, 

　　　　　　　　{BIG,1350,BIG,0,BIG,1200}, 

　　　　　　　　{BIG,2350,2550,BIG,0,850}, 

　　　　　　　　{BIG,BIG,BIG,1200,850,0}, 

　　　　　　　　};

//Dijkstra算法函數，求給定點到其餘各點的最短路徑 

//參數：鄰接矩陣、頂點數、出發點的下标、結果數組、每個點的前趨 

void Dijkstra(int Cost[][6],int n,int v0,int Distance[],int pre[]) 

{ 

　　int s[6]; 

　　int mindis,dis; 

　　int i,j,u; 

　　//初始化 

　　for(i=0;i<n;i++) { 

　　　　Distance[i]=Cost[v0][i]; 

　　　　s[i]=0; 

　　} 

　　s[v0] =1; //标記v0 

　　//在目前還未找到最短路徑的頂點中，尋找具有最短距離的頂點 

　　for(i=0;i<n;i++){ 

　　　　if(Distance[i]<BIG) pre[i]=v0; 

　　} 

　　for(i=1;i<n;i++) { //每循環一次，求得一個最短路徑 

　　　　mindis=BIG; 

　　　　for (j=0;j<n;j++) //求離出發點最近的頂點 

　　　　　　if(s[j]==0&&Distance[j]<mindis) { 

　　　　　　　　mindis=Distance [j]; 

　　　　　　　　u=j; 

　　　　　　} 

　　　　for(j=0;j<n;j++) //修改遞增路徑序列（集合） 

　　　　　　if(s[j]==0) { //對還未求得最短路徑的頂點 

　　　　　　　　//求出由最近的頂點 直達各頂點的距離 

　　　　　　　　dis=Distance[u] +Cost[u][j]; 

　　　　　　　　//如果新的路徑更短，就替換掉原路徑 

　　　　　　　　if(Distance[j]>dis){ 

　　　　　　　　　　Distance[j]=dis; 

　　　　　　　　　　pre[j]=u; 

　　　　　　　　} 

　　　　　　} 

　　　　s[u]=1; // 标記最短路徑已經求得 

　　} 

}

用Dijkstra函數算出最短路徑後，就可以遞歸出從給定頂點到各點的最短路徑上的每個點了，函數如下（不含終點）：

char pathres[100]=""; //儲存路徑 

char *Vertex[6]={"福州","上海","廣州","北京","成都","西安"}; 

//參數：起點、終點 

void shpath(int st,int ed) //起點應該為Dijkstra函數中的v0 

{ 

　　if(pre[ed]!=st){ 

　　　　shpath(st,pre[ed]); 

　　} 

　　strcat(pathres,Vertex[pre[ed]]); 

　　strcat(pathres,"-"); 

} //最後要在主函數中把終點加到pathres裡