数据结构-Astar算法-最短路径

以下程序根据网上公布的源码改写，若有侵权，请联系我，我将删除此博文。

#include<iostream>
#include<queue>
#include<math.h>
#include<fstream>
using namespace std;

typedef struct node
{
 char ch;//当前点属于何种类型——障碍物、开始点、目标点
 int x,y;//当前点的坐标
 float h_cost,g_cost;//估价函数f_cost=h_cost+g_cost;h_cost为当前点的目标点的估计耗费，g_cost为移动到当前点的耗费。
 bool visited;//是否访问过
 node *father;//指向父点的指针
 node()//当前点初始化
 {
  visited=0;
  father=NULL;
 }
};
node map[50][50];//地图50x50
node start,dst;//开始点和目标点
bool is_in_map(int x,int y)//判断是否在地图内
{
 if (x>=0&&x<50&&y>=0&&y<50)
      return true;
 return false;
}
int max(int a,int b) {return a>b?a:b;}
float Manhattan_dis(int sx,int sy,int ex,int ey){//曼哈顿
 float nn;
 nn=abs(sx-ex)+abs(sy-ey);
 nn*=10;
 return nn;
}

float Euclidean_dis(int sx,int sy,int ex,int ey){//欧几里德
 float nn;
 nn=((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey));
 return sqrt(nn);
}

float Chebyshev_dis(int sx,int sy,int ex,int ey){//切比雪夫
 float nn;
 nn=max(abs(sx-ex),abs(sy-ey));
 return nn;
}

float jiaquan_Manhattan(int sx,int sy,int ex,int ey){//加权曼哈顿   //better
 float nn,dx,dy;
 dx=abs(sx-ex);
 dy=abs(sy-ey);
 if(dx>dy)
  nn=10*dx+6*dy;
 else
  nn=6*dx+10*dy;
 return nn;
}

bool operator<(node a,node b){
 return a.g_cost+a.h_cost>b.g_cost+b.h_cost;
}
int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//上下左右方向
//A*算法
int Astar(){
 priority_queue <node> q;//优先队列
 q.push(start);//将开始点压入队列
 node now;//当前点
 int xx,yy;//当前点移动后坐标
 int i;//循环变量

 while(!q.empty()){//当队列不为空时
  now=q.top();//取出队列顶部节点作为当前点
  q.pop();//将当前点从队列删除
  if(now.x==dst.x && now.y==dst.y)//如果当前点为目标点
   break;
  //移动当前点
  for(i=0;i<4;i++){
   xx=now.x+direction[i][0];
   yy=now.y+direction[i][1];
   //若是不在地图内或者是障碍物或者是已经搜索过的点则忽略
   if(!is_in_map(xx,yy) || map[xx][yy].ch=='x' || map[xx][yy].visited==1)
    continue;
   //生成新的节点
   map[xx][yy].father=&map[now.x][now.y];
   map[xx][yy].visited=1;//已经搜索过

   map[xx][yy].h_cost=jiaquan_Manhattan(xx,yy,dst.x,dst.y);//选择想用的h(x)

   map[xx][yy].g_cost=now.g_cost+1;

   q.push(map[xx][yy]);
  }
 }
 return 0;
}

int viewback(){
 node *p;
 p=map[dst.x][dst.y].father;//从目标点开始画最短路径
 while(p){
  if(p->father)
   p->ch='v';//最短路径字符
  p=p->father;
 }
 return 0;
}

int main(){
 int i,j,numVisited=0;
 ifstream pfile("test2.txt");
 while(!pfile.eof())
 {
  for(i=0;i<50;i++){
   for(j=0;j<50;j++){
    pfile>>map[i][j].ch;//读入每一字符赋给地图数组
    map[i][j].x=i;
    map[i][j].y=j;
    if(map[i][j].ch=='s'){//如果是开始点
     map[i][j].g_cost=0;
     map[i][j].visited=1;

     start=map[i][j];
    }
    if(map[i][j].ch=='e')//如果是目标点
     dst=map[i][j];
   }
  }
 }
 cout<<"结果---------------------------------------------------"<<endl;
 Astar();//搜索最短路径
 viewback();//画最短路径

 for(i=0;i<50;i++){
  for(j=0;j<50;j++){
   numVisited+=map[i][j].visited;
   if(map[i][j].ch=='v' )
    {
         printf("%c",map[i][j].ch);
          }
   else if(map[i][j].visited)//打印搜索标记
    printf("%d",map[i][j].visited);
   else
    printf("%c",map[i][j].ch);
  }
  cout<<"\n";
 }
 printf("\n遍历节点 %d 个\n",numVisited);
 return 0;
}