第k短路 算法详解（图解）与模板（A* 算法）

A是一种启发式搜索，根据目标地点和当前点的距离和估计要走的步数来决策下一步走哪个方向。而这两个参数，一般用$g(x)$和$h(x)$，其中$g(x)$为$x$点到目标点的实际距离。 所以最终的我们要走哪个点取决于$g(x)+h(x)$，取可选点中$g(x)+h(x)$最优的那个点走。 *而k短路，就是终点第K次被找到的时候。

---

随便从网上扒了一份图，根据图来详细了解下 这份图因为在博客园出现过，在简书也出现过，且都未标注原创是谁，所以这里我直接拿来用了，如有侵权，请回复，我会删除此文

---

现在来看看图，现在我们要从$A$点走到$B$点，假设我们可走8个方向（$↑，↓，←，→，↖，↗，↙，↘$）。（后文均用箭头代指方向） 先求出实际花费（就是↑，↓，←，→，↖，↗，↙，↘8个点到$B$点的最短路，用Dijkstra或者SPFA等常用最短路算法跑一遍就行了） 尊重原图，这里设每走一格花费为10，所以走第一步的$g$如下： ↑：50(表示从$A$向上走一步再走到$B$的最短路长为50，注意这里的50是从$A$->$A↑$到$B$的最短路，不是从$A↑$到$B$的最短路。下同) ↓：50 ←：50 →：30 ↖：60 ↗：40 ↙：60 ↘：40 上图中左下角为到B点的估算值$h（x）$, 右下角为 实际距离。左上角为二者之和。最短路问题，走过了该点就不再走第二次了，所以我们把$A，C$点标记，不再进入这2个点。然后再根据$C$点的可行路径，在所有可走范围内再次寻找加权和最小的那点，这里我们用优先队列实现这个不断BFS搜寻可行路，并且不断取出加权和最小的点的过程 最终结果如下：

#include <map>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn =  1e3+5;
const int INF = 0x3f3f3f3f;

int  s,t,k;
bool vis[maxn];     //标记该点是否已经经过
int dis[maxn];      //从起点实际到终点的路径，为上文中的g（x）
struct node{
    int v,c;
    node(int _v=0,int _c=0) : v(_v),c(_c) {};    //构造
    node(){};
    bool operator < (const node & buf) const{       
        return c+ dis[v]  > buf.c + dis[buf.v];
    }
};

struct edge{
    int v,cost;
    edge(int _v=0,int _c=0) : v(_v),cost(_c){};
};

vector <edge> e[maxn],reve[maxn];      //反向存图,这样从终点找一次单源最短路即可求出dis
priority_queue<node> q;
void dijkstra(int n,int s){     //dijkstra+队列优化求出dis数组的内容
    mem(vis,false);
    mem(dis,0x3f);
    while(!q.empty()) q.pop();
    dis[s] = 0;
    q.push(node(s,0));
    while(!q.empty()){
        node tmp = q.top();
        q.pop();
        int u = tmp.v; 
        if(vis[u])
            continue;
        vis[u] = true;
        fori(e[u].size()){
            int v = e[u][i].v;
            int cost = e[u][i].cost;
            if(!vis[v] && dis[v] > dis[u] + cost){
                dis[v] = dis[u] + cost;
                q.push(node(v,dis[v]));
            }
        }
    }
}


int aStar(int s){  //S为起点
    while(!q.empty()) q.pop();      
    q.push(node(s,0));
    k--;          
    while(!q.empty()){
        node pre = q.top();
        q.pop();
        int u = pre.v;
        if(u == t){         //到达终点
            if(k)   k--;    //不是第K次就继续找
            else    return pre.c;
        }
        for(int i=0;i<reve[u].size();i++){  //将当前点所有能经过的点扔进优先队列
            int v = reve[u][i].v;
            int c = reve[u][i].cost;    //这里的h（x）我们取通过这条边的实际花费
            q.push(node(v,pre.c+c));
        }
    }
    return -1;      //找不到K短路
}

void addedge(int u,int v,int w){    
    reve[u].pb(edge(v,w));  //反向存图
    e[v].pb(edge(u,w));     //正向存图
}
int main() {
    IO;
    int n,m,u,v,w;
    while(cin>>n >> m){
        fori(n+2){
            e[i].clear();
            reve[i].clear();
        }
        fori(m){
            cin >> u >> v >> w;
            addedge(u,v,w);
        }
        cin >> s >> t >> k;
        dijkstra(n,t);
        if(dis[s] == INF)
            cout << -1 << endl;
        else{
            if(s == t)
                k ++;  ///如果起点==终点不能算上dis = 0 的这一点
            cout << aStar(s) << endl;;
        }
    }
    return 0;
}

---

A的时间复杂度取决于h（x）函数的选择，在网上并未找到具体的分析，不过需要注意的是，如果图为n元环，A算法的时间花费将会是指数级的（摘自wiki），一般遇到这类问题的时候，都是采用可持久化可并堆进行优化，具体怎么优化。。。。。蒟蒻博主还未学习学会了再来贴上代码和分析~~~