寻路算法实现

实现任意两点间的寻路，自动选择最优或较优路径

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里