第k短路
n个点，m条边的有向图，给出起点s，终点t，求s到t的第k，短路。
1.2 问题分析
- 一条路径可以由两部分组成，第一部分是一个从起点
s出发到达任意点x的路径，而第二部分是从x出发，到终点t的最短路径。两部分正好可以组成一条s~t的路径，且每一条路径都可以分解这两部分（允许任意一部分为空）。
- 因此当我们已知第一部分的路径
A时，设第二部分为B，我们可以尝试预估完整的路径A+B的费用（距离）
- 估价函数为：
f(x)=g(x)+h(x)。其中g(x)表示路径s~x的已知长度，而h(x)表示路径x~t的预估最短距离。
- 求最短路时，我们用的是松弛算法，
x到起点s只保留最短的路径，但求第k短路每一条路径都需要保留。
1.3 算法流程
- 对原图建一个反图，求出终点
t到任一点的最短距离，相当于求出了任一点到t的最短路，把它当做修正函数h(x)。如果t到s的最短路不存在，则无解。
- 从起点
s开始，扩展其邻接边x，把扩展出来的每一条路径加入到优先队列里，优先队列维护的是对股价函数f(x)=g(x)+h(x)进行排序的小根堆，g(x)表示x到起点s的某一条路径的实际值，h(x)是x到终点t的最短距离。
- 用数组
cnt[x]记录节点x出堆的次数，显然出堆次数表示起点s到x目前的路径条数，所以当cnt[u]==k时说明目前已经有k条不同的s到t的路径。为了保证第k短，每次我们把队首最小的路径出队，并以此点扩展路径，显然先出队的路径比后出队的路径更短。
1.4 代码实现
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1000+5,maxm=1e5+5,Inf=0x3f3f3f3f;
struct Node{
int pos,hx,gx;
Node(){};
Node(int x,int y,int z){pos=x;hx=y;gx=z;}
bool operator < (const Node &a)const{
return hx+gx>a.hx+a.gx;
}
};
struct Edge{
int to,w,next;
}e[maxm],re[maxm];
int head[maxn],rhead[maxn],dis[maxn],vis[maxn];
int n,m,s,t,k;
void Insert(int u,int v,int w){
e[++head[0]].to=v;e[head[0]].w=w;e[head[0]].next=head[u];head[u]=head[0];//原图
re[++rhead[0]].to=u;re[rhead[0]].w=w;re[rhead[0]].next=rhead[v];rhead[v]=rhead[0];//反图
}
void spfa(){//对反图跑最短路，求出终点t到任意点的最短路
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[t]=0;vis[t]=1;q.push(t);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=rhead[u];i;i=re[i].next){
int v=re[i].to;
if(dis[v]>dis[u]+re[i].w){
dis[v]=dis[u]+re[i].w;
if(!vis[v]){
q.push(v);vis[v]=1;
}
}
}
}
}
int astar(){
if(dis[s]==Inf)return -1;//t到s不可达
int cnt[maxn]={0};//cnt[i]记录节点i的出队次数
priority_queue<Node> q;
q.push(Node(s,0,0));//s:起点,第二为h(s),第三位g(s)
while(!q.empty()){
Node temp=q.top();q.pop();
int u=temp.pos,gx=temp.gx;
cnt[u]++;//节点u的出队次数
if(cnt[u]==k && u==t)return gx;
if(cnt[u]>k)continue;//只需记录起点到u的不超过k条路径，多的路径没意义
for(int i=head[u];i;i=e[i].next){//从u扩展其他路径
int v=e[i].to,w=e[i].w;
q.push(Node(v,dis[v],gx+w));
}
}
return -1;//队列为空u出队次数不到k次，说明不存在第k短路。
}
void Solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
Insert(u,v,w);
}
scanf("%d%d%d",&s,&t,&k);
if(s==t)++k;
spfa();
printf("%d
",astar());
}
int main(){
Solve();
return 0;
}
- 此题求得是不严格的第k短路，如果要求严格的最短路改怎么办呢？