Dijkstra 算法

基本算法

Dijkstra 算法可以用于求解某个点到其他所有点的最短路径长度。

挑选某个源点 s，使用小根堆记录 [节点，源点到此节点的距离]，按照到此节点的距离组织小根堆。使用 vis 数组记录点是否已访问过，dist 数组记录到某节点的最短距离（初始设为无穷）。

然后，将 [s, 0] 加入小根堆。

接下来，反复取出堆顶元素 [u, 源点到 u 的距离]：

• 若 vis[u] == true，说明已经定下了到 u 的最短距离，忽略，继续循环
• 否则，令 vis[u] = true，然后考察 u 的所有连边（假设去往 v，边权为 w），若 vis[v] == false 且 dist[u] + w < dist[v]，说明路径更短，将 dist[v] 更新为 dist[u] + w，将 [v, dist[v]] 加入小根堆

堆为空则结束，此时 dist 记录了源点到每个点的最短距离。

P4779 【模板】单源最短路径（标准版）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
bool vis[N]; // 记录节点是否访问过
int dist[N]; // 记录源点到某节点最短距离
struct record {
    int node, length; // 存放 [节点，到节点的最短距离]
};
bool operator<(record a, record b) { return a.length > b.length; }
priority_queue<record> pq;
vector<record> G[N];
int main()
{
    int n, m, s; cin >> n >> m >> s;
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    for (int i = 1; i <= n; ++i) {
        dist[i] = 1e9 + 1; // 初始化为很大的数
    }
    
    pq.push({s, 0}); // 将 [s, 0] 加入堆
    dist[s] = 0; // s 到自己肯定为 0
    while (pq.size()) {
        record e = pq.top();
        pq.pop();
        int u = e.node;
        if (vis[u]) continue; // 已经弹出过了，则忽略
        vis[u] = true; // 标记已访问过
        for (auto adj : G[u]) {
            int v = adj.node;
            int w = adj.length;
            if (!vis[v] && dist[u] + w < dist[v]) { // 发现更小的，更新
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) cout << dist[i] << ' ';
    return 0;
}

反向索引堆优化

分层图

对一张图进行搜索或者求最短路时，不一定要把实际的节点作为节点，而是将 [节点编号，与节点有关的状态] 作为节点，例如：