图论---第k短路

poj2249

A*算法

来自百度百科
A* 算法，A* （A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

公式表示为： $f(n) = g(n) + h(n)$ ,

其中， $f(n)$ 是从初始状态经由状态 $n$ 到目标状态的代价估计，
$g(n)$ 是在状态空间中从初始状态到状态 $n$ 的实际代价，
$h(n)$ 是从状态 $n$ 到目标状态的最佳路径的估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）

$h(n)$ 的选取:
保证找到最短路径（最优解的）条件，关键在于估价函数 $f(n)$ 的选取（或者说 $h(n)$ 的选取）。

我们以 $d(n)$ 表达状态 $n$ 到目标状态的距离，那么 $h(n)$ 的选取大致有如下三种情况：

如果 $h(n)< d(n)$ 到目标状态的实际距离，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 $h(n)=d(n)$ ，即距离估计 $h(n)$ 等于最短距离，那么搜索将严格沿着最短路径进行，此时的搜索效率是最高的。
如果 $h(n)>d(n)$ ，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
所以取 $h(n) \le d(n)$

模板

求一个图中从源点 $s$ 到终点 $t$ 的第 $k$ 短路

定义数组d[n],表示从 $n$ 到 $t$ 的距离，以 $t$ 为源点做一次最短路可以得到每个点到 $t$ 的距离，所以要存一个反向图，用来预处理d[n]，直接以d[n]当作 $h(v)$

有了d[n]之后，维护一个优先队列，队列中的每个节点都存放{v,sum},v表示当前点，sum表示到达点v一共走了多少距离。优先队列按照公式 $f(v) = g(v) + h(v)$ 确定优先级，其中 $g(n)$ 对应sum, $h(v)$ 对应d[v]，通过优先队列一次次的扩展，如果第 $k$ 此取到 $t$ ，那么此时的sum就是 $s$ 到 $t$ 的 $k$ 短路。

$f(v)$ 其实就是s-v的距离加上v-t的距离，这就是一条路，我们可以知道每条路长度，所以可以找到第k短的那一条，每次取到t，就是找到了一个比上次次短的路.
例题 POJ2249

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
#define MAXN 100009

int n,m,s,t,k; 
int d[MAXN];// 每个点到t的距离
const int inf = 0x3f3f3f3f;
struct  edge{
    int to,len,next;
}e1[MAXN], e2[MAXN];

struct  node{//优先队列中的节点
    int v,sum;
    node(int v,int w):v(v),sum(w){}
    bool operator < (const node & o)const{
        return  this->sum+d[this->v] > o.sum+d[o.v];  // 这里就是估值小的放前面，f(v) = g(v) + h(v)，sum就是g(v),d[]做h(v)
    }
};
int head1[MAXN], head2[MAXN] , js1,js2; //分别存 原图，反向图
bool vst[MAXN];
void init(){
    js1 = 0;js2 = 0;
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
}
void add1(int a, int b, int len){//建原图
    e1[js1].to = b;
    e1[js1].len = len;
    e1[js1].next = head1[a];
    head1[a] = js1;
    js1++;
}
void add2(int a, int b, int len){//建反向图
    e2[js2].to = b;
    e2[js2].len = len;
    e2[js2].next = head2[a];
    head2[a] = js2;
    js2++;
}
void spfa(){//用反向图初始化d[]
    queue<int> que;
    que.push(t);
    memset(vst,0,sizeof(vst));
    memset(d,inf,sizeof(d));
    d[t]=0;
    vst[t]=1;
    while(!que.empty()){
        int u=que.front(); que.pop();
        vst[u]=0;
        for(int i=head2[u]; i!=-1; i=e2[i].next){
            int v=e2[i].to;
            int w=e2[i].len;
            if(d[u]+w < d[v]){
                d[v] = d[u]+w;
                //cout<<d[v]<<endl;
                if(!vst[v]){
                    vst[v]=1;
                    que.push(v);
                }
            }
        }
    }
}
int astar(){//A* 算法
    if(d[s]==inf) return -1;//说明没有s到t的通路
    priority_queue<node> que;
    que.push(node(s,0)); //从s出发
    int cnt=0; //记录到达了多少次
    while(!que.empty()){
        node u = que.top(); que.pop();
        if(u.v == t){
            cnt++;
            if(cnt == k)return u.sum;
        }
        for(int i=head1[u.v]; i!=-1; i=e1[i].next){
            int v=e1[i].to;
            int w=e1[i].len;
            que.push( node(v, u.sum+w) );
        }
    }
    return  -1; //不存在k短路
}
int main(){
    
    scanf("%d %d",&n, &m);
    init();
    for(int i=0;i<m;i++){
        int a,b,len;
        scanf("%d %d %d",&a,&b,&len);
        add1(a,b,len);
        add2(b,a,len); //反向图
    }
    scanf("%d %d %d",&s,&t,&k);
    if(s==t)k++;  //poj2449这道题中，如果st重合，那么第一短结果肯定是0，原地不动不当作一条路看
    spfa();//初始化估计值 d[]
    int ac = astar();
    printf("%d\n",ac);
    return 0;
}