最短路

最短路问题即，给你一张图，让你求出图中两点的最短距离。

这篇文章会讲解 \(Dijkstra\)、\(Spfa\)、\(Floyd\) 三种算法，让您透彻理解最短路！

Dijkstra

朴素版

题目：

\(Dijkstra\) 通常是用来解决图中一个定点到其余点的最短距离，基本思路是：从中心向外扩展，直到扩展到终点为止。

我们用 \(dist[u]\) 来表示从源点 \(s\) 到 \(u\) 的最短距离。

还需要维护一个状态数组 \(st\)，用于在更新最短距离时，判断当前的点的最短距离是否需要更新（是否已经确定）。

在每一次扩展的过程中，我们要先找到当前未确定的点的集合中找到一个距离最小的点，也就是：

int t = -1; // 距离最短的点的编号
for (int j = 1; j <= n; ++j) 
    if (!st[j] && (t == -1 || dist[j] < dist[t])) // 判断是否符合条件
        t = j;

那么我们就已经确定这个点了，把它的状态更新一下：

st[t] = true;

然后用这个点更新所有未确定点的最短距离

for (int j = 1; j <= n; ++j) 
    if (!st[i]) // 这句话其实可以不用加，因为我们dijkstra算法的性质已经确定后面确定的点不会再比现在的小了
        dist[j] = min(dist[j], dist[t] + g[t][j]);

完整代码：

#include <iostream>
#include <cstring>
#define N 510
using namespace std;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; // 源点到源点的距离是0
    for (int i = 1; i <= n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) 
            if (!st[j] && (t == -1 || dist[j] < dist[t])) 
                t = j;
        st[t] = true;
        for (int j = 1; j <= n; ++j) dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == 0x3f3f3f3f) return -1; // 不存在最短路径
    return dist[n];
}
int main() {
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c); // 防止重边的情况
    }
    cout << dijkstra() << '\n';
    return 0;
}

此代码时间复杂度为 \(O(n^2)\)。

优化

我们发现，朴素 \(Dijkstra\) 主要就耗时在找 \(t\) 上了；在一组数中找到一个最小值，我们自然可以想到用小根堆（不推荐手写）。

于是我们的代码就可以优化成这样了：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define N 200000
typedef pair<int, int> PII; // 存储距离和节点编号
int n, m;
int h[N], e[N], w[N], ne[N], idx; // 因为是点数较多，所以用邻接表存图
int dist[N];
bool st[N];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                q.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << '\n';
    return 0;
}

剩下的咕咕，明天再写。