做這個題算是學了學spfa算法，一開始感覺spfa和dij好像；dij找最小點松弛，spfa就是一個一個的松弛，松到不能松。

求S到T的第K短路

思路：這個算法的思路是從源點S優雅的暴力跑bfs，用優先隊列來裝跑的過程中點的位置以及跑的距離，優先隊列按照來裝跑的距離最短的排序，然后隨著跑跑的距離就越來越長，那總會跑到T點吧，這個時候你的cnt+1，直到第k次跑到T點的時候就是第K短路了。看著很迷，但是為什么說是優雅呢，就是該算法的核心，A*就是Astar算法

1.首先，從終點T跑一邊Spfa，用數組d[ ]記錄每一個點到終點T的最短距離。

2.然后，從起點S跑bfs，邊跑邊記錄跑的距離F與位置now，優雅的就是，當我們每次跑到一個位置的時候，其實從位置now到T點的最短的距離G又確定了，G=F+d[now],然后我們結構體裝進去位置，已經跑的距離，從該點跑到T點的最短距離{now,F，G}，并且按照G點排序，當我們走到終點now=T，這個時候就是第一次跑到G點的時候，那么F就是第一短的距離，那么跑到第k次終點T，此時的F就是第K短路。

參考博客：https://blog.csdn.net/z_mendez/article/details/47057461? 超級清晰的介紹

代碼如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const double eqs=1e-9;
const double pi=acos(-1.0);
const double E=2.718281828459;
using namespace std;
const int maxm=1e5+5;
const int maxn=1005;
int d[maxn],head[maxn],rhead[maxn];
int vis[maxn],n,m,t,k;
struct Edge
{int to,p,val;
}edge[maxm<<1],redge[maxm<<1];
struct node
{int now,g,f;bool friend operator<(node s,node e){if(s.f==e.f) return s.g>e.g;return s.f>e.f;}
};
void init()
{for(int i=0;i<=n;i++){d[i]=inff;head[i]=rhead[i]=-1;vis[i]=0;}
}
void add(int u,int v,int val,int sign)
{redge[sign]=Edge{u,rhead[v],val};rhead[v]=sign;edge[sign]=Edge{v,head[u],val};head[u]=sign;
}
void Spfa(int u)
{queue<int> q;d[u]=0;q.push(u);while(!q.empty()){u=q.front();q.pop();vis[u]=0;for(int i=rhead[u];~i;i=redge[i].p){int v=redge[i].to;if(d[v]>d[u]+redge[i].val){d[v]=d[u]+redge[i].val;if(!vis[v]){q.push(v);vis[v]=1;}}}}
}
int Astar(int s)
{priority_queue<node>q;int cnt=0;if(s==t) k++;///如果是起點等于終點k++if(d[s]==inff) return -1;node a,next;a=node{s,0,d[s]};q.push(a);while(!q.empty()){a=q.top();q.pop();if(a.now==t){cnt++;if(cnt==k)return a.g;}for(int i=head[a.now];i!=-1;i=edge[i].p){next.now=edge[i].to;next.g=a.g+edge[i].val;next.f=next.g+d[next.now];q.push(next);}}return -1;
}
int main()
{int s,x,y,z;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z,i);}scanf("%d%d%d",&s,&t,&k);Spfa(t);printf("%d\n",Astar(s));}return 0;
}

?

總結

以上是生活随笔為你收集整理的poj 2449 Remmarguts' Date 启发式搜索 A*算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。