以前所接触过的最短路径算法是dijkstra或floyd之类的，都是在已知每两点之间距离的情况下求最短路的。
那么想一下这样的案例
给你一个地图，类似于迷宫一样，中间有些障碍物，再给定起点终点，求该两点间最短路，显然，上述两种算法就不适用了，因为提到的迷宫，我们可能会很容易想到广搜bfs，但一次bfs下来实际上求出了起点到所有点的最短路径，但我们只想知道它与终点间的最短路径，也就是说这个方案里有很多冗余的操作。
说到这里，该步入正题，介绍A*算法。
A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。(取自百度百科)
何谓直接搜索方法，即不进行任何预处理直接进行搜索的方法。
那么它为何可以称为最有效的直接搜索方法呢，我们看到上文说到一个估价值与估价函数。
所以有这么一个式子
f(n) = g(n) + h(n)
先记住这个式子，在讨论这个式子之前，先谈点题外话。
我们都接触过贪心思想，即在对问题求解时，总是做出在当前看来是最好的选择。
从起点开始，它可走的地方是周围的8个点(最多)，平常广搜时多个可能是平等对待，全部考虑。
那么？我们可不可以运用贪心的思想从8个点中选出一个最有可能达到最短路的点来优先进行操作呢？
当然可以，这样我们就是有针对性的搜索，而不是盲目搜索了。
有的道友可能会说了，这样贪心下来求出的只能是接近于最优解的相对最优解，并不能保证一定最优，没错，事实的确是这样。
那么这样就行不通了，因为我们的目的是很明确的，要的是最短路径。
但是往常的贪心算法都是选取当前状态下最好的选择，至于次好选择等等全部就丢掉了，那如果我们仍然保留这些选择，仍与后来的可能进行比较呢，这样就保证最后的解一定是最优解了。
如何将所有可能性都保留下来继续参与后来的比较呢，优先队列是一个不错的法子。
1. 从A开始，将其周围可走且未标记的点，全部加入队列，然后标记A点
2. 从队列中选取优先度最高的点B
3. 对B重复1操作，直到到达终点为止
但优先度如果获得呢，现在我们回到这个式子
f(n) = g(n) + h(n)
g(n)为从起点到点n所花费的代价值
h(n)为点n到终点所花费代价的估价值
两者之和 f(n)就是点n的优先值
例如，对几何地图进行求解时，可以将从起点到点n走的步数作为g(n)，将点n到终点的几何距离作为h(n)估价值，那么此时，f(n)的值越小，优先度越高。
下面贴代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<functional>
#include<set>
using namespace std;
const int N = 10009;//地图范围
int v[N][N] = {};//记录地图
int dx[] = {1,1,1,0,0,-1,-1,-1};//8个方向
int dy[] = {1,0,-1,1,-1,1,-1,0};
int f[N*N];//对当前点进行标记，同时记录上一个位置的坐标
struct Node
{
int x,y,f,g;//坐标与权值
};
struct Nodecmp//优先队列比较函数
{
bool operator() (const Node &a, const Node &b)
{
return a.f > b.f;
}
};
int leng(Node a, Node b)//求点与终点的几何长度
{
return sqrt((a.x - b.x)*(a.x - b.x)
+ (a.y - b.y)*(a.y - b.y));
}
void print(int nid, int n)//输出最短路径
{
if(nid == -1)
return;
print(f[nid],n);
printf("%d %d\n",(nid-1)/n, nid-(nid-1)/n*n);
}
bool a_start(Node s, Node e, int n)
{
if(!v[e.x][e.y])//终点不可达
return false;
memset(f, 0, sizeof(f));
priority_queue<Node, vector<Node>, Nodecmp> q;
int eid = e.x * n + e.y;
f[s.x * n + s.y] = -1;//二维转一维进行标记，便于操作
while(!q.empty())
{
Node now = q.top();
q.pop();//出队
int nid = now.x * n + now.y;
if(nid == eid)//判断是否为终点
{
print(nid, n);
return true;
}
for(int i=0;i<8;i++)//遍历8个方向
{
Node t;
t.x = dx[i] + now.x;
t.y = dy[i] + now.y;
int tid = t.x * n + t.y;
if(v[t.x][t.y] && f[tid] == 0)
{//符合条件便标记并入队
f[tid] = nid;
t.g = now.g + 1;
t.f = t.g + leng(t, e);
q.push(t);
}
}
}
return false;
}
int main()
{
int n;
Node s,e;
s.g = 0;
cin>>n>>s.x>>s.y>>e.x>>e.y;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>v[i][j];
if(!a_start(s,e,n))
cout<<"无法到达"<<endl;
}