python

10 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `178` 第`K`短路

A星算法详解(个人认为最详细,最通俗易懂的一个版本)

一、题目描述

给定一张 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

输入样例：

输出样例：

二、暴力+`Dijkstra`

在Dijkstra堆优化算法中，如果我们每次找到 距离最短的一个点 去 更新其它点 ，当 目标点 出队第K次的时候，当前的距离就是从起点到目标点的 第K短路

`Code`

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 1e4 + 10;

// 本题由于是有向图，并且，允许走回头路（比如有一个环存在，就可以重复走，直到第K次到达即可，这与传统的最短路不同）,所以，没有st数组存在判重

int n, m;   // n个顶点,m条边
int S, T;   // 起点与终点
int K;      // 第K短的路线
int cnt[N]; // 记录某个点出队列的次数

int h[N], w[M], e[M], ne[M], idx; // 邻接表
int dist[N];                      // 到每个点的最短距离
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

struct N1 {
    int u, d;
    const bool operator<(const N1 &b) const {
        return d > b.d; // 谁的距离短谁靠前
    }
};

// 小顶堆
priority_queue<N1> q;
// 堆优化版本Dijkstra
void dijkstra() {
    // 起点入队列
    q.push({S, 0});

    while (q.size()) {     // bfs搜索
        int d = q.top().d; // 当前点和出发点的距离
        int u = q.top().u; // 当前点u
        q.pop();
        cnt[u]++; // 记录u节点出队列次数

        if (u == T) {            // 如果到达了目标点
            if (cnt[u] == K) {   // 第K次到达
                printf("%d", d); // 输出距离长度
                return;
            }
        }
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            /*
            对比标准版本 Dijkstra
            if (!st[u]) {
            st[u] = 1;
                for (int i = h[u]; ~i; i = ne[i]) {
                    int v = e[i];
                    if (d[v] > dist + w[i]) {
                        d[v] = dist + w[i];
                        q.push({d[v], v});
                    }
                }
            }
            ① 取消了st[u]:因为一个点可以入队列多次
            ② 不是最短的才可以入队列，是谁都可以
            */
            if (cnt[v] < K)
                q.push({v, d + w[i]}); // 不管长的短的，全部怼进小顶堆，不是最短路径才是正解，是所有路径都有可能成为正解！所以，这里与传统的Dijkstra明显不一样！
        }
    }
    puts("-1");
}

// 通过了 6/7个数据
// 有一个点TLE，看来暴力+Dijkstra不是正解

int main() {
    // 初始化邻接表
    memset(h, -1, sizeof h);

    // 寻找第K短路，n个顶点，m条边
    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c; // a->b有一条长度为c的有向边
        add(a, b, c);
    }

    cin >> S >> T >> K; // 开始点，结束点，第K短

    if (S == T) K++; // 如果S=T，那么一次检查到相遇就不能算数，也就是要找第K+1短路

    // 迪杰斯特拉
    dijkstra();

    return 0;
}

三、`Dijkstra`+`A*`寻路

设置这么一个 估价函数

F = G + H G ：该点到起点的距离 H ：该点到终点的距离

每一次进行更新距离时，同时更新 估价函数F ，使用 优先队列(堆) 维护。

`Q`:估计函数作用是什么？为什么估价函数是取每个点到终点的最短距离?

答：相当于在搜索的过程在做贪心的选择,这样我们可以优先走那些可以 尽快搜到终点 的路。比如有1w条路，让找第10短的路，那么，我们就把最短，次短，次短的...优先整完，这样，第10短的就快找到了。

原始版本的Dijkstra算法中，第一次出队的都是最短的路，并且，加上了st标识，这样就很快。到了第K短的路，就不敢加st限制，因为人家可以走多次。那每次都是取最短的行不行呢？其实是不行的。以上面的　链接　为例，明知道目标在墙的后面，但我们还是在南辕北辙的向左侧去扩展，虽然现在看起来　已完成距离短，但不是真的短，本质上应该是　离出发点距离　+　到目标点的最短距离　最短，才是真的最短。　

这题的估价函数就是第k短路 >= 最短路。真妙。先建立反向图，跑一次dijkstra把每个点到终点的最短路求到。

然后AStar跑一边，这题真是对比dijkstra和AStar的异同点。一个重要优化是如果一个点出队K次了，他就没有必要在入队了。

Code

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 1010;
const int M = 200010;
int n, m;
int S, T, K;
int h[N], rh[N];
int e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int cnt[N];

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

// 只有点号和距离时，按距离由小到大排序
struct N1 {
    int u, d;
    const bool operator<(const N1 &b) const {
        return b.d < d; // 谁的距离短谁靠前
    }
};

// 当有点号+距离+估值函数时，按估值函数值由小到大排序
struct N2 {
    int u, d, f;
    const bool operator<(const N2 &b) const {
        return b.f < f;
    }
};

// 经典的Dijkstra,计算终点到图中其它所有点的最短路径
void dijkstra() {
    priority_queue<N1> q;
    q.push({T, 0});

    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    while (q.size()) {
        N1 t = q.top();
        q.pop();
        int u = t.u;
        if (st[u]) continue;
        st[u] = true;
        for (int i = rh[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] > dist[u] + w[i]) {
                dist[v] = dist[u] + w[i];
                q.push({v, dist[v]});
            }
        }
    }
}

int astar() {
    priority_queue<N2> q;
    q.push({S, 0, dist[S]}); // 起点入队列

    while (q.size()) {
        int u = q.top().u;
        int d = q.top().d;
        q.pop();
        cnt[u]++;                            // u出队一次
        if (u == T && cnt[u] == K) return d; // 找到到终点的第K短路

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] < INF)                             // 如果是无效借力点，跳过
                q.push({v, d + w[i], d + w[i] + dist[v]}); // 点，距离，估值函数值
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);   // 正向图
    memset(rh, -1, sizeof rh); // 反向图

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);  // 正向建图，常规逻辑
        add(rh, b, a, c); // 反向建图，用于获取终点t到图中所有点的最短路径。为估值函数作准备
    }

    cin >> S >> T >> K;

    // ① 如果起点与终点最开始是一样的，那么就需要入队列k+1次,这是一个坑
    if (S == T) K++;

    // ② 先跑一遍Dijkstra,方便计算出估值函数
    dijkstra();

    // ③ 利用Dijkstra计算出来的终点到任意点的值，再加上当前走过的距离，等于AStar的估值函数
    cout << astar() << endl; // A*算法
    return 0;
}

`Q:`为什么要加一句：`if (dist[v] < INF)` ，不加不行吗？

答：

此处代码有两种写法：

网上大神写法：

for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (cnt[v] < K)
                q.push({v, d + w[i], d + w[i] + dist[v]});
        }

我的写法：

  for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] < INF)                             // 如果是无效借力点，跳过
                q.push({v, d + w[i], d + w[i] + dist[v]}); // 点，距离，估值函数值
        }

原因：见AcWing给出错误时的数据用例：

感悟

① 自我认为我的办法才是正解，因为你想把估值函数入队列，还指望着函数值小的优先，那如果d + w[i] + dist[v]>=INF，再往里放就是无效操作，而dist[v]是有可能等于INF的，因为

\large S->v-\ngtr T

此时，v就是 一个无效转移点，不用入队列，一次都不用！ ② 通过错误的 数据用例 来反思、推导，加深理解非常重要,此处给AcWing满分，比某谷要强的多！与学会自我创造测试用例一样有用，在以后的学习中一次要重视起来。

10 KiB Raw Permalink Blame History Unescape Escape

AcWing 178 第K短路

一、题目描述

二、暴力+Dijkstra

Code

三、Dijkstra+A*寻路

Q:估计函数作用是什么？为什么估价函数是取每个点到终点的最短距离?

Q:为什么要加一句：if (dist[v] < INF) ，不加不行吗？

感悟