首页 > 代码库 > POJ 2449 A*+SPFA
POJ 2449 A*+SPFA
A*算法求第k短路流程：
1）计算h[]，即当前点到t的估计值
若为有向图，建立反向图求出h[]。若为无向图，可直接求解h[]。可通过SPFA求解。
2）A*搜索
每次找到新节点就直接加入队列，计算出估价函数f[]=g[]+h[]，然后加入优先队列中。（此步不可优化，否则可能造成失解）
常用STL priority_queue实现，要注意默认是大根堆，可重载<实现小根堆。
3）若根入队k次，返回
ADD：
该题几个注意事项及优化：
a）若起始点h值==INF，不搜。
b）若一个点入队超过k次，不搜。
c）邻接表代替邻接矩阵，防止重边。
d）该题中若s==t，距离为0的路径不能计入。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define N 1005#define M 100005using namespace std;struct Edge{ int y,w,ne;}e[M*2],re[M*2];int x,y,w,n,m,s,t,k;int be[N],all;int rbe[N],rall;int h[N],cnt[N];bool vis[N];struct Point{ int x,g; bool operator < (const Point T) const { return g+h[x]>T.g+h[T.x]; }};void add(int x, int y, int w){ e[all].y=y; e[all].w=w; e[all].ne=be[x]; be[x]=all++;}void radd(int x, int y, int w){ re[rall].y=y; re[rall].w=w; re[rall].ne=rbe[x]; rbe[x]=rall++;}void SPFA(int s){ queue< int > q; while(!q.empty()) q.pop(); for(int i=0; i<=n; i++) { h[i]=INF; vis[i]=0; } h[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=rbe[u]; i!=-1; i=re[i].ne) { int v=re[i].y; if(h[v]>h[u]+re[i].w) { h[v]=h[u]+re[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } }}int Astar(int s, int t, int k){ SPFA(t); if(h[s]==INF) return -1; priority_queue< Point > q; while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); Point cur,nxt; cur.x=s; cur.g=0; q.push(cur); while(!q.empty()) { cur=q.top(); q.pop(); if((++cnt[cur.x])>k) continue; if(cnt[t]==k) return cur.g; for(int i=be[cur.x]; i!=-1; i=e[i].ne) { nxt.x=e[i].y; nxt.g=cur.g+e[i].w; q.push(nxt); } } return -1;}void init(){ all=0; memset(be,-1,sizeof(be)); rall=0; memset(rbe,-1,sizeof(rbe));}int main(){ scanf("%d%d",&n,&m); init(); for(int i=0; i<m; i++) { scanf("%d%d%d",&x,&y,&w); add(x,y,w); radd(y,x,w); } scanf("%d%d%d",&s,&t,&k); if(s==t) k++; printf("%d\n",Astar(s,t,k)); return 0;}/*2 41 2 11 2 21 2 32 1 51 2 5*/
POJ 2449 A*+SPFA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。