Dijkstra

这是一份关于“无向有权图最短路径”的题解。

题目解析

这道题目是一个标准的单源最短路径问题。

• 目标：找到从起点 $1$ 到终点 $n$ 的最短路径，并输出路径上的节点序列。
• 图的特点：无向图、边权为正整数（$w \ge 1$）。
• 数据规模：$n, m \le 10^5$。

由于边权均为正数，Dijkstra 算法是解决此问题的最佳选择。我们需要在计算最短距离的同时，记录每个节点的前驱节点，以便最后还原路径。

---

解题思路

1. 算法选择：

   • 使用 Dijkstra 算法配合**优先队列（堆）**优化。
   • 时间复杂度为 $O((N+M)\log N)$，对于 $10^5$ 的数据规模是可以接受的。

2. 数据结构：

   • 邻接表：用于存储图，节省空间。
   • 距离数组 dist[]：dist[i] 表示从起点 $1$ 到节点 $i$ 的当前最短距离，初始化为无穷大，dist[1] = 0。
   • 前驱数组 pre[]：pre[i] 记录在最短路径上，节点 $i$ 的前一个节点是谁。这是还原路径的关键。

3. 路径还原：

   • 当 Dijkstra 算法结束后，如果 dist[n] 仍然是无穷大，说明无法到达，输出 -1。
   • 否则，从终点 $n$ 开始，利用 pre[] 数组不断向前回溯直到起点 $1$，将经过的节点存入列表，最后反转列表输出。

---

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

vector<vector<pair<int, int>>> adj;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    adj.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<long long> dist(n + 1, INF);
    vector<int> pre(n + 1, -1);
    
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pre[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[n] == INF) {
        cout << -1 << endl;
    } else {
        vector<int> path;
        int curr = n;
        while (curr != -1) {
            path.push_back(curr);
            curr = pre[curr];
        }
        
        reverse(path.begin(), path.end());

        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

---

关键点说明

1. dist 数组类型：
   由于边权 $w$ 最大为 $10^6$，路径最长可能经过 $10^5$ 条边，总距离可能达到 $10^{11}$，超过了 int 的范围，所以 dist 数组建议使用 long long。

2. pre 数组初始化：
   pre 数组初始化为 -1。起点 $1$ 的前驱保持为 -1，这作为路径回溯的终止条件。

3. 优先队列优化：
   使用 priority_queue 配合 greater 来实现小顶堆，确保每次取出的都是当前距离起点最近的未确定节点。

4. 路径回溯：
   从终点 $n$ 开始，通过 pre[n] 找到上一个点，直到回溯到 -1。得到的序列是 $n \to \dots \to 1$，所以最后必须使用 reverse 函数将其翻转为 $1 \to \dots \to n$。