短路與和短路或的區別，K短路 A*

一、k短路

什么是k短路？最短路就是第一短路，那么第k短的就是k短路。

二、求k短路

首先可以想到在BFS中，從起點開始走，把每個點放入隊列中時，以當前走過的距離加上當前點到終點的最短距離的和（即我們假設可以預知走哪個點到終點的距離最短）作為比較條件從小到大排序，當第一個到達終點時，走過的路徑長度即為最短路，那么第

k次到達終點的長度顯然就是k短路。

短路與和短路或的區別，那么接下來就是問題的核心了，如何判斷哪個點到終點的距離最短呢？即如何可以每次都優先走最有希望到達終點的點？

這里就要用到啟發式搜索了，要用到一個啟發函數：f=h+g,? ?h為當前搜索的代價，g為估計函數，這個估計必須小于等于實際值。

h好求，就是當前走過的路徑，g呢？估計值不妨就取當前點到終點的最短路徑，即等于實際值。放入優先隊列中，每次都先出h+g的和小的。當終點第k次出隊時，當前終點走過的的路徑就是k短路的長度。或者當某個點第k次出隊時，答案就是這個點的f的值。

啟發式搜索實際上就是避免了一些無謂的搜索，使搜索的方向能夠朝向正確的方向進行。

關于g的求法，即構建反向邊，從終點跑一次最短路即可。

還要注意的一點是，當s==t時，起點和終點一樣的時候，因為一定要走距離，所以要k++

B1005K線對地短路什么意思、下面以poj2449為例，給出模板

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI  acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x)  priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
const int N=1e5+10;
int n,m,s,t,k;
ll dis[N];
int head[N],rhead[N];
bool vis[N];
struct edge
{int to,ne;ll val;
}e[N],re[N];
int tot1,tot2;
void add1(int x,int y,int z)//正向邊
{e[++tot1].to=y;e[tot1].ne=head[x];e[tot1].val=z;head[x]=tot1;
}
void add2(int x,int y,int z)  //加反向邊
{re[++tot2].to=y;re[tot2].ne=rhead[x];re[tot2].val=z;rhead[x]=tot2;
}
struct node  //a*的結構體
{int to;ll val;bool operator < (const node &c)const{return val+dis[to]>c.val+dis[c.to];   //按照f值從小到大的排序，即先出最有可能到達終點的點}node(int _to,ll _val):to(_to),val(_val){};
};
struct qnode
{int v;int c;qnode(int _v=0,int _c=0):v(_v),c(_c){}bool operator <(const qnode &r)const{return c>r.c;}
};
void init()
{tot1=-1;tot2=-1;met(head,-1);met(rhead,-1);
}
bool dj()
{memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)dis[i]=inf;priority_queue<qnode>que;while(!que.empty())que.pop();dis[t]=0;que.push(qnode(t,0));qnode tmp;while(!que.empty()){tmp=que.top();que.pop();int u=tmp.v;if(vis[u])continue;vis[u]=true;for(int i=rhead[u];i!=-1;i=re[i].ne){int v=re[i].to;int cost=re[i].val;if(!vis[v]&&dis[v]>dis[u]+cost){dis[v]=dis[u]+cost;que.push(qnode(v,dis[v]));}}}return dis[s]!=inf;
}
ll a_star()
{int cnt=0;priority_queue<node>que;que.push(node(s,0));while(!que.empty()){node now=que.top();que.pop();if(now.to==t){k--;if(k==0){return now.val;}}for(int i=head[now.to];~i;i=e[i].ne)que.push(node(e[i].to,now.val+e[i].val));//這里壓入隊列的now.val+e[i].val是已走過的長度}return -1;
}
int main()
{while(~scanf("%d%d",&n,&m)){init();int x,y;ll z;for(int i=1;i<=m;i++){scanf("%d%d%lld",&x,&y,&z);add1(x,y,z);add2(y,x,z);}scanf("%d%d%d",&s,&t,&k);if(dj()){if(s==t)k++;printf("%lld\n",a_star());}else printf("-1\n");}
}

?