最短路 | 山暮云秋

Dijkstra 单源带权(朴素)

Dijkstra 朴素算法

1、最短路 1：给定 $n$ 个点 $m$ 条边的有向图($n \leq 1000$)，输出点 $1$ 到 $n$ 的最短距离。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边。如果不存在路径，输出 $-1$
2、先前在图与回溯中介绍过权值相等最短路(无权最短路)，现在有了权值，需要做一个结构体保存。Dijkstra还使用一个数组 $d[]$ ，$d[i]$ 表示从起点 $st$ 到 $i$ 的最短距离
3、Dijkstra 思路如下图：起始时，建图，标记所有 $d[i]$ 为 $\infty$，以 $1$ 为起点，向外走一层，将经过的边松弛(用边的权值更新所到点的 $d[i]$ ，$d[i]$ 取较小值)；接下来，比较得到最小的 $d[i]$ ，以该点为当前起点(图中为点 $2$)，先前的点已经可以忽略，继续向外走一层，将经过的边松弛(注意，$d[3]$ 取较小值更新为 $3$)；以此类推，以 $4$ 为当前起点发现点 $4$ 没有出点，返回；以 $3$ 为当前起点，走到终点，更新 $d[5]$ 为 $6$，所以最短路为 $6$
4、该算法结合了贪心和DP的思想，每个点只拓展一次，且拓展时已为最短距离

代码实现

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

// 一个十六进制的 3f 对应二进制的 0011 1111 (恰好 8 bit = 1 Byte)，因此 int 写 4 个 3f
// 用 3f 表示无穷的好处是，该值可以安全地乘 2 或做一些运算而不溢出
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;

// 出边
struct Edge
{
    // x 表示出点，w 表示权值
    int x, w;
};

vector<Edge> g[N]; // g 是一个 vector<Edge> 的数组
int d[N];          // d[i] 表示从起点 st 到 i 的最短距离
int n, m;

// Dijkstra 朴素
void Dijkstra(int st)
{
    memset(d, INF, sizeof(d)); // 初始化 d[i] 为 INF
    d[st] = 0;                 // 起始点 d[st] 为 0
    bitset<N> vis;             // 标记是否拓展过

    // 进行 n 轮检验
    for (int i = 1; i <= n; i++)
    {
        // 找出 d[i] 最小点 u
        int u = 1;
        for (int j = 1; j <= n; j++)
            // 如果当前的点 u 未被拓展(被拓展过就必须更换) 或 (d[j] < d[u] 且 j 未被拓展)
            if (vis[u] || !vis[j] && d[j] < d[u])
                u = j;

        // 此时 u 点为 d[i] 最短点，d[u] 为当前最优长度
        // 从 u 点向下松弛，开始拓展，标记 vis[u]
        vis[u] = true;
        // 遍历所有 u 的出边
        for (auto &[v, w] : g[u])
            // 如果 v 未被拓展 且经 u 到 v 的总距离比原先(可能的) d[v] 更短
            if (!vis[v] && d[u] + w < d[v])
                d[v] = d[u] + w; // 更新 d[v]
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        // 判断不是自环
        if (u != v)
            g[u].push_back({v, w}); // 存储有向图
    }

    Dijkstra(1);

    cout << (d[n] != INF ? d[n] : -1);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

Dijkstra 单源带权(堆优化)

Dijkstra 堆优化

1、最短路 2：给定 $n$ 个点 $m$ 条边的有向图($m \leq 10^5$)，输出点 $1$ 到 $n$ 的最短距离。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边。如果不存在路径，输出 $-1$
2、数据量变大，原先的朴素算法中由于有 $O(n^2)$ 会超时，可以用优先队列(堆)优化程序。优先队列中存储点和起点到该点的总距离，设定为小根堆，确保堆顶元素的总距离最短，因此堆顶即为每次 $d[i]$ 最小的点，便不需要查找了
3、起始，将起点入队，每次获取起点(且从队中弹出)并向外走一层，像朴素算法一样将边松弛(维护 $d[i]$)，同时将新点入队。只要队列不为空，就继续执行这一过程

代码实现

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

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;

// 出边
struct Edge
{
    // x 表示出点，w 表示权值
    int x, w;
};

// 定义 < 比较规则
bool operator<(const Edge &u, const Edge &v)
{
    // 注意：优先队列通过 < 成立得到大根堆，所以需要小根堆则在比较中应使用 > 比较
    // 用 > 比较 w，保证堆顶元素 w 最小(总路径最短)
    return u.w > v.w;
}

vector<Edge> g[N]; // g 是一个 vector<Edge> 的数组
int d[N];          // d[i] 表示从起点 st 到 i 的最短距离
int n, m;

// Dijkstra 堆优化
void Dijkstra(int st)
{
    memset(d, INF, sizeof(d)); // 初始化 d[i] 为 INF
    d[st] = 0;                 // 起始点 d[st] 为 0
    bitset<N> vis;             // 标记是否拓展过

    // 使用优先队列(堆)优化，需要定义 Edge 的 < 比较规则，小根堆
    priority_queue<Edge> pq; // pq 中的 w 表示从起点到当前点的总距离
    pq.push({st, d[st]});    // 初始化 pq，将起点入队

    // pq 不为空，能够找到新的点就继续循环
    while (!pq.empty())
    {
        int x = pq.top().x; // 取出堆顶元素(w 最小)的 x 作为起点(即朴素算法中查找 d[i] 最小的点)
        pq.pop();           // 弹出当前点

        // 如果拓展过，就跳过
        if (vis[x])
            continue;
        vis[x] = true; // 标记当前点被拓展

        // 遍历当前最小点 x 的所有出边，向外走一层
        for (auto &[y, w] : g[x])
        {
            // 如果 y 未被拓展 且经 x 到 y 的总距离比原先(可能的) d[y] 更短
            if (!vis[y] && d[x] + w < d[y])
            {
                // 不能在此处标记 vis[y]，否则 d[y] 之后将无法更新
                d[y] = d[x] + w;    // 更新 d[y]
                pq.push({y, d[y]}); // 当前 y 点入队
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        // 判断不是自环
        if (u != v)
            g[u].push_back({v, w}); // 存储有向图
    }

    Dijkstra(1);

    cout << (d[n] != INF ? d[n] : -1);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

Floyd 多源带权

Floyd 多源带权最短路

1、最短路 3：给定 $n$ 个点 $m$ 条边的有向图($n \leq 300$)，有 $q$ 次询问，每次输入 $u v$，输出从 $u$ 到 $v$ 的最短距离(若不存在则输出 $-1$)。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边，再给出这 $q$ 次询问，每次输入所询问的 u, v
2、该题询问任意两点的最短距离，是多源最短路。Floyd的证明十分复杂，因此在此只介绍用法，当作模板背过即可。对于图中任意两点 $i, j$，定义 $d[i][j]$ 表示 $i$ 到 $j$ 当前的最短距离，但我们并不关心两点间的路径；我们使用三层循环，最外层遍历一个中转点 $k$，内两层分别遍历起点 $i$ 和终点 $j$，则有结论 $d[i][j] = d[i][k] + d[k][j]$ ($i$ 到 $j$ 的距离 $= i$ 到 $k$ 的距离 $+ k$ 到 $j$ 的距离)，再将该结果与原先 $d[i][j]$ 取较小值更新 $d[i][j]$ 。全部操作后，$d[i][j]$ 便直接是最短路径长度
3、这只是一个非常宏观的结论(因为根本不关心具体路径如何)，把结论背过即可。注意：起始应使用邻接矩阵建图，且该图也直接充当 $d[][]$ 数组，在其上更新数据；开始时需要初始化数组为无穷，初始化自环距离为 $0$；输入可能有重边，取更短值；特别注意，必须最外层枚举中转点 $k$ ，其次是 $i$ ，再其次是 $j$ ，否则结论不成立

代码实现

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

const int INF = 0x3f3f3f3f;
const int N = 310;
int d[N][N]; // 邻接矩阵 兼 处理最短路的数组
int n, m, q;

// Floyd 算法
void Floyd()
{
    // 默写结论，注意枚举时 k 在最外层
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void solve()
{
    cin >> n >> m >> q;

    // 初始化 d 数组为无穷
    memset(d, INF, sizeof(d));
    // 初始化自环距离为 0
    for (int i = 1; i <= n; i++)
        d[i][i] = 0;

    // 输入并建图
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w); // 可能有重边，取较小值
    }

    Floyd();

    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << (d[u][v] != INF ? d[u][v] : -1) << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

Dijkstra 单源带权(朴素)

Dijkstra 单源带权(堆优化)

Floyd 多源带权

页底评论