AcWing 178：第K短路 ← A* 算法

【题目来源】
https://www.acwing.com/problem/content/description/180/

【题目描述】
给定一张 N 个点（编号 1,2…N），M 条边的有向图，求从起点 S 到终点 T 的第 K 短路的长度，路径允许重复经过点或边。
注意：每条最短路中至少要包含一条边。

【输入格式】
第一行包含两个整数 N 和 M。
接下来 M 行，每行包含三个整数 A，B 和 L，表示点 A 与点 B 之间存在有向边，且边长为 L。
最后一行包含三个整数 S，T 和 K，分别表示起点 S，终点 T 和第 K 短路。

【输出格式】
输出占一行，包含一个整数，表示第 K 短路的长度，如果第 K 短路不存在，则输出 −1。

【数据范围】
1≤S,T≤N≤1000,
0≤M≤10^4,
1≤K≤1000 ,
1≤L≤100

【输入样例】
2 2
1 2 5
2 1 4
1 2 2

【输出样例】
14

【算法分析】
一、A* 算法简介
A* algorithm is a popular choice for graph search. Breadth First Search is the simplest of the graph search algorithms. Graph search algorithms, including A*, take a “graph” as input.
A* algorithm is a modification of Dijkstra’s Algorithm that is optimized for a single destination.
A* algorithm uses both the actual distance from the start and the estimated distance to the goal.
From: https://www.redblobgames.com/pathfinding/a-star/introduction.html

二、A* 算法的估值更新
A* 算法的估值更新，需要用到 A* 算法的启发函数 h(x)。
相应地，A* 算法的可表示为：f(x)=g(x)+h(x)，其中：
f(x)：从初始状态经由当前状态 x 到目标状态的估计代价
g(x)：从初始状态到当前状态 x 的实际代价
h(x)：从当前状态 x 到目标状态的估计代价

注意：
1. 针对 f(x)=g(x)+h(x)，如果 h(x)=0，就是普通的BFS算法；如果 g(x)=0，就是贪心算法。所以 A* 算法就是“BFS+贪心”。
2. 启发函数 h(x) 决定了A*算法的优劣。启发函数 h(x) 包括曼哈顿距离、对角线距离（切比雪夫距离）、欧几里得距离等。启发函数 h(x) 必须满足单调性（即估计代价不会超过从当前状态 x 到目标状态的的实际代价）。A*算法的主要难点是设计合适的 h(x) 函数，而编码很容易。
3. 在二维平面上，有3种方法可以近似计算 h(cur)。
下面的 (cur.x, cur.y) 是 cur 点的坐标，(t.x, t.y) 是终点 t 的坐标。
（1）曼哈顿距离
应用场景：只能在四个方向（上，下，左，右）移动。
h(cur)=abs(cur.x–t.x)+abs(cur.y–t.y)
（2）对角线距离
应用场景：可以在八个方向上移动，例如国际象棋的国王的移动。
h(cur)=max(abs(cur.x–t.x), abs(cur.y–t.y))
（3）欧几里得距离。
应用场景：可以向任何方向移动。
h(cur)=sqrt((cur.x–t.x)^2+(cur.y–t.y)^2)
非平面问题，需要设计合适的 h 函数。
4. 计算 h(x) 时，要忽略路径中的障碍物。因为 h(x) 是对剩余距离的估算值，而不是实际值，因此 h(x) 为估计代价。
5. A*算法中，地图必须是可行的，即不存在无法通过的障碍物或无法到达的区域。同时，需将地图“网格化”，“网格化”其实就是将连续的问题离散化。
6. A*算法中，选取下一个格子的标准并不是离终点最近，而是离起点和终点的距离之和最近。

三、A* 算法的步骤
在 A* 算法中，需要使用两个辅助表来记录结点。
一个用于记录可被访问的结点，称为 openList 表；一个是记录已访问过的结点，称为 closeList 表。
A* 算法的终止条件是终点在 closeList 表中（找到路径）或 openList 表为空（找不到路径）。
-------------------------------------
A* 算法的简单步骤如下：
1.把起始节点添加到openList；
2.重复如下步骤：
a) 寻找 openList 当中 F 值最低的结点，将其称为当前结点；
b) 将该结点从 openList 中删除，并加入 closeList 当中；
c) 对于当前结点相邻的 8 个结点
* 如果它不可通过或者已在 closeList 当中，忽略它，反之如下；
* 如果它不在 openList 当中，将其添加进去。把当前结点作为它的父结点。同时更新它的 F，G 和 H 值。
* 如果它已经在 openList 当中，通过判断沿当前结点到它的路径的 G 值是否更小，若更小，则将当前结点作为它的父结点，同时更新它的 F 和 G 值。否则，不做任何操作。
d) 当目标结点已添加到 closeList 时，路径已被找到；或者没有找到目标结点，此时 openList 已为空。这时候，路径不存在。以上两种情况结束循环。
3.路径回归。从目标结点开始，沿着每一个结点的父结点移动至起始结点，形成的路径即为所求路径。

【算法代码】
代码来源于：https://www.acwing.com/solution/content/21233/

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N=1005,M=2e5+5;
int e[M],ne[M],h[N],val[M],idx,rh[N];
int dist[N],cnt[N];
bool st[N];
int n,m,S,T,K;

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

void dijkstra() {
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,T});
    memset(dist,0x3f,sizeof dist);
    dist[T]=0;

    while(heap.size()) {
        auto t=heap.top();
        heap.pop();

        int cur=t.second;
        if(st[cur]) continue;
        st[cur]=true;

        for(int i=rh[cur]; i!=-1; i=ne[i]) {
            int j=e[i];
            if(dist[j]>dist[cur]+val[i]) {
                dist[j]=dist[cur]+val[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int astar() {
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S],{0,S}});
    while(heap.size()) {
        auto t=heap.top();
        heap.pop();
        int cur=t.second.second,distance=t.second.first;
        cnt[cur]++;

        if(cnt[T]==K) return distance;

        for(int i=h[cur]; i!=-1; i=ne[i]) {
            int j=e[i];
            if(cnt[j]<K) {
                heap.push({distance+val[i]+dist[j],{distance+val[i],j}});
            }
        }
    }
    return -1;
}

int main() {
    cin>>m>>n;
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);
    for(int i=0; i<n; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        add(h,a,b,c);
        add(rh,b,a,c);
    }

    cin>>S>>T>>K;
    if(S==T) K++;
    dijkstra();

    cout<<astar();
    return 0;
}

/*
in:
2 2
1 2 5
2 1 4
1 2 2

out:
14
*/

【参考文献】
https://www.acwing.com/solution/content/21233/
https://www.jianshu.com/p/b010a81c2754
https://mp.weixin.qq.com/s/ojRrD4zboF7LVYSwOkWcgQ
https://zhuanlan.zhihu.com/p/595716772
https://zhuanlan.zhihu.com/p/385733813
https://blog.csdn.net/hnjzsyjyj/article/details/126693357
https://cdn.acwing.com/blog/content/38521/
https://www.acwing.com/solution/content/49264/
https://www.redblobgames.com/pathfinding/a-star/implementation.html
https://www.redblobgames.com/pathfinding/a-star/implementation.cpp
https://mp.weixin.qq.com/s/f8SihfGy2VCj5th8IaiLsQ