第k短路(A*)

Acwing 算法提高课第k短路(A*)

使用A*的线索

本题要求的是第k短路，也就是要考虑浩瀚的搜索空间，所以我们需要一种强而有力的搜索方式

估价函数

对于第k短路,它的路径长度一定>=最短路, 所以我们可以令当前点到终点的最短距离作为估价函数用【算法竞赛进阶指南】上的话来讲:既可以保证f(x) <= g(x)又可以顺应g(x)的变化趋势

如何求每个点到终点的最短距离

反向建边,跑一遍dijkstra()

那么具体如何实现求第k短路呢

首先一个比较直观的想法就是:终点第一次弹出时是最短路,那么当终点第k次弹出时是否为第k短路?

我们可以尝试使用数学归纳法证明:

$已知前k-1短路已经被弹出,假设此时弹出的不是第k短路$ $Dist > dist_{k}$ $若点u是第k短路上的一个点,则有dist_{k} >= dist_{u} + f_{u}$ $又\because 小根堆 \therefore Dist <= dist_{u} + f_{u}$ $\therefore 得证$

最后整理一下思路：
 用dijkstra求每个点到终点的最短路作为估价函数
 若此时起点的距离为正无穷说明不连通可直接判为无解
 用A-star求出第k短路
 注意:I.  是否入队无关是否能更新，因为不是求最短路
      II. 当一个点已经被入队k次了却还没有找到第k短路,则第k短路不经过这个点无需重复入队

对于 II.参考于OIwiki

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

const int N = 1e3 + 10, M = 2e4 + 10;
typedef pair<int, int> PII; //用于Dijkstra堆优化
typedef pair<int, PII> PIII;//用于A-stra维护 距离和,真实距离,节点

int n, m, s, ed, k;
int h[N], rh[N], w[M], e[M], ne[M], idx;//正反边
int dist[N];
bool st[N];//用于dijkstra

void add(int h[], int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dijkstra(){
    priority_queue<PII, vector<PII>, greater<PII> > heap;//建堆
    heap.push({0, ed});
    memset(dist, 0x3f, sizeof dist);
    dist[ed] = 0;//不要忘记初始化起点
    
    while(heap.size()){
        PII t = heap.top();
        heap.pop();
        
        int ver = t.y, dis = t.x;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = rh[ver]; ~i; i = ne[i]){//注意这里是反边
            int j = e[i];
            if(dist[j] > dis + w[i]){
                dist[j] = dis + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int cnt[N];//用于统计每一个点出队几次(同时用于剪枝和求第k短路)

int Astar(){
    priority_queue<PIII, vector<PIII>, greater<PIII> > heap;
    heap.push({dist[s], {0, s}});
    while(heap.size()){
        PII t = heap.top().y;
        heap.pop();
        int ver = t.y, dis = t.x;
        
        //在出队时统计,不能在入队时统计
        cnt[ver] ++;      
        
        if(ver == ed)//终点出队时
            if(cnt[ver] == k)return dis;//第k短路
        
        for(int i = h[ver]; ~i; i = ne[i]){//拓展(extend)
            int j = e[i];
            
            //这个很重要,当起点和终点只有一条路径且其它支路中有环会死循环
            if(cnt[j] >= k) continue; 
            
            heap.push({dist[j] + dis + w[i], {dis + w[i], j}});
        }
    }
    return -1; //无解
}

int main(){
    freopen("KthPath.in", "r", stdin);
    freopen("KthPath.out", "w", stdout);
    
    //init
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    cin >> s >> ed >> k;
    if(s == ed) k ++; //处理起点终点重合情况
    
    dijkstra();
    
    if(dist[s] == 0x3f3f3f3f){//不连通
        puts("-1");
        return 0;
    }
    
    printf("%d\n", Astar());
    
    return 0;
}

起点与终点不连通
3 2
1 2 3
2 1 3
1 3 1
起点与终点连通但是无第k短路
4 4
1 2 1
2 3 1
3 2 1
1 3 1
1 3 2

Acwing 算法提高课 第k短路(A*)