第k短路学习笔记

第k短路学习笔记

十月 20, 2020

参考资料

第k短路(Dijkstra&A*)

第k短路和次短路

A*(第k短路)

1.什么是第k短路？第一短路就是最短路，以此类推。求某点s到某点e的第k短路就是k短路问题

2.思路：

（1）我们知道在BFS中，第一次到达终点就是到终点的最短路，那么第k次到达终点，当然就是到终点的第k短路了。但是如果直接BFS搜索下去，时间复杂度会非常高，因此我们需要剪枝，怎么剪枝呢？

（2）我们每次只需要取出每次到达终点最有希望的路径，就避开了一些没有意义的到其他点的路径。因此我们需要一个启发函数。令f = x + h（其中x为到当前点的实际距离，h为从当前点到达终点的估测最短距离），则f就估测为从起点到终点的路径长度，我们每次只要有目的有方向的前进到达终点k次即为k短路

（3）那么怎么求这个h呢？h其实为每个点到达终点的最短路，但是我们只学过某个点到其他点的最短路怎么办？当然是把终点当作起点跑最短路啊（哇笨蛋) ， 但是这里有一个问题：我们需要在跑终点最短路时使用反向边，跑BFS时使用正向边（有向图），为什么呢：

3.求解步骤

（1）Dijkstra求终点到其他点的最短路

（2）正向边跑起点的BFS（以A*启发函数：f = x + h为排序，取出点）

例题：POJ-2449

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
///poj上提交编译错误 不过板子大概没问题

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<int,int>
const ll Max=1e3+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;
/*
*/
vector<P>mp[Max],invmp[Max];
bool vis[Max];
int n,m;
int disT[Max],vistime[Max];
void Dijkstra(int start){
    for(int i=0;i<=n;i++)disT[i]=inf;
    priority_queue<P,vector<P>,less<P> >q;
    disT[start]=0;
    q.push({0,start});
    while(!q.empty()){
        P temp=q.top();q.pop();
        int now=temp.second;
        if(vis[now])continue;
        vis[now]=1;
        for(auto edge:invmp[now]){
            int cost=edge.second,to=edge.first;
            if(disT[now]+cost<disT[to]){
                disT[to]=disT[now]+cost;
                q.push({disT[to],to});
            }
        }
    }
}
int Astar(int start,int endpoint,int k){
    //memset(vis,0,sizeof vis);
    if(disT[start]==inf)return -1;
    priority_queue<P,vector<P>,greater<P> >q;
    q.push({disT[start],start});
    while(!q.empty()){
        P temp=q.top();q.pop();
        int now=temp.second,ExpectCost=temp.first;
        vistime[now]++;
        if(vistime[now]==k&&now==endpoint)return ExpectCost;
        if(vistime[now]>k)continue;
        for(auto edge:mp[now]){
            int Cost=edge.second,to=edge.first;
            q.push({ExpectCost-disT[now]+Cost+disT[to],to});
        }
    }
    return -1;
}
int main() {
    Turnoff;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,val;
        cin>>u>>v>>val;
        mp[u].push_back({v,val});
        invmp[v].push_back({u,val});
    }
    int S,T,K;cin>>S>>T>>K;
    Dijkstra(T);
    int ans=Astar(S,T,K);
    cout<<ans<<endl;
}