本文主要是介绍poj2449-A*算法+优先队列+第k最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
分析：A*算法主要由是估价函数f(n)=g(n)+h(n);其中g(n)代表当前的实际代价。h(n)是估计代价。算法的效率直接取决于h(n)的评价性。h(n)的设计思想是无限靠近（极限）.
在本题中，g(n)代表从初始位置到当前x点所付出的代价。h(n)代表从当前x点到目标位置的估计代价。本题关键是怎样求h(n)，每个点到目标点t不一定联通。也不好估价，
巧妙之处是：从目标t到初始位置s的最短路。即反向求最短路。这样h(n)的值是最低评估了。
代码;
#include<cstdio>
#include<queue>
#include<cstring>
#define N 1001
#define INF 1000000
using namespace std;struct qu{ //优先队列 int v,g,h; qu(int V,int G,int H):v(V),g(G),h(H){} //构造函数 bool operator<(const qu &a)const{ //运算符重载 return a.g+a.h<g+h; //A_star 算法的体现之处 }
};struct node{int x,y,cost,next1,next2;
}edge[N*200];bool vis[N];
int s,t,k,n,m,cnt;
int hash[N],head[N],d[N];bool spfa() //反向求最短路，即求评估函数h，结果保存在d【】中。
{queue<int>q;int i,x,v;memset(vis,0,sizeof(vis));for(i=1;i<=n;i++) d[i]=INF;d[t]=0;q.push(t);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(i=head[x];i!=-1;i=edge[i].next2){v=edge[i].x;if(d[v]>edge[i].cost+d[x]){d[v]=edge[i].cost+d[x];if(!vis[v]){vis[v]=1;q.push(v); }}}}if(d[s]==INF) return false;return true;
}int A_star()
{ int count[N],p;if(!spfa()) return -1; //即判定是否连通，又求出了评估函数。 if(s==t) k++; //这个要注意。相同的不能认为第k短路是0，而是1，而这里求得为0，故要加1. memset(count,0,sizeof(count));priority_queue<qu>Q;Q.push(qu(s,0,d[s]));while(!Q.empty()){qu dx=Q.top();Q.pop();if(count[dx.v]==k) continue;if(++count[dx.v]==k&&dx.v==t) return dx.g; //因为是优先队列，第几次出列，即就是第k短路 for(int i=hash[dx.v];i!=-1;i=edge[i].next1){p=edge[i].y;if(count[p]==k) continue;Q.push(qu(p,dx.g+edge[i].cost,d[p]));}}return -1;
}void addate(int x,int y,int c) //要求双向，故要两个表
{edge[cnt].x=x;edge[cnt].y=y;edge[cnt].cost=c;edge[cnt].next1=hash[x];edge[cnt].next2=head[y];hash[x]=cnt;head[y]=cnt++;
}int main()
{int x,y,c,i;cnt=0;scanf("%d%d",&n,&m); memset(head,-1,sizeof(head));memset(hash,-1,sizeof(hash));for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);addate(x,y,c);}scanf("%d%d%d",&s,&t,&k);printf("%d\n",A_star());return 0;
}
这篇关于poj2449-A*算法+优先队列+第k最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
