跳到主要内容

AcWing 849. Dijkstra 求最短路 I

本节目标

用 O(n²) 邻接矩阵 Dijkstra 求解非负权有向图中从 1 号点到 n 号点的最短距离。

这是最短路的矩阵版母题。它把非负权单源最短路写成“选出最小候选、确定、松弛”的固定循环。

查看 AcWing 原题

题意与约束​

给定 n 个点和 m 条有向正权边，求从 1 到 n 的最短距离；不可达输出 -1。n ≤ 500，可以用邻接矩阵保存图，重边取较小权值，自环不会改善正权最短路。

直接思路与瓶颈​

可以枚举从 1 到 n 的所有路径并取最短，但带环图的路径数会爆炸；即使限制为简单路径，枚举也不适合 n ≤ 500。另一种做法是反复扫描所有边来改进距离，却没有说明哪个点的答案已经不会再变，也会做许多重复松弛。这里的边权均为正数，适合利用这个单调性逐点确定答案。

图模型与算法推导​

将有向图存成邻接矩阵 graph：没有边为无穷大，重边取较小权值。令 vis 表示已经确定最短距离的集合，dist[v] 是目前已发现的从 1 到 v 的最短候选。每轮在线性扫描中选未访问且 dist 最小的点，加入 vis；再扫描它在矩阵中的整行，尝试 dist[vertex] + graph[vertex][nxt] 松弛所有 nxt。

剩余候选全为无穷大时，后续顶点都不可达，应立即停止；这也避免把无穷大参与无意义加法。

正确性依据​

归纳证明每次加入 vis 的点距离正确。初始时 1 号点距离为 0，显然正确。假设已确定集合内各点都正确，取未访问点中 dist 最小的 vertex。若存在更短的 1 到 vertex 路径，它第一次离开已确定集合时会经过一条从已确定点到未确定点的边；该边在相应已确定点被选中时已经松弛，因边权非负，得到的候选不会大于这条路径到达 vertex 前的距离，和 vertex 是最小候选矛盾。因此 vertex 可安全确定。松弛其出边后，所有经过新确定点的一跳延伸都被纳入候选，归纳成立。

样例执行过程​

输入：

3 3
1 2 2
2 3 1
1 3 4

矩阵中 1→2=2、2→3=1、1→3=4。初始 dist=[0, ∞, ∞]、vis=∅（下标依次为 1、2、3）。

  1. 选距离最小的 1，加入 vis={1}；扫描第 1 行，得到 dist=[0, 2, 4]。
  2. 在未访问点中选 2，加入 vis={1,2}；用 2→3=1 松弛，dist[3] 从 4 改为 3，即 dist=[0, 2, 3]。
  3. 选 3，加入 vis={1,2,3}；没有更优后继。最终 dist[3]=3，输出 3，路径为 1→2→3。

代码实现​

main() 只读入、建图和输出，dijkstra() 只负责选点与松弛。两份代码都用最小重边初始化矩阵。

C++17
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

const long long INF = numeric_limits<long long>::max() / 4;

long long dijkstra(const vector<vector<long long>>& graph, int source, int target) {
    const int n = static_cast<int>(graph.size()) - 1;
    vector<long long> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    dist[source] = 0;
    for (int round = 0; round < n; round++) {
        // 选出当前未确定的最短路顶点
        int vertex = -1;
        for (int cand = 1; cand <= n; cand++) {
            if (!vis[cand] &&
                (vertex == -1 || dist[cand] < dist[vertex])) {
                vertex = cand;
            }
        }

        // 最小候选仍不可达时，后续顶点也都不可达
        if (vertex == -1 || dist[vertex] >= INF / 2) {
            break;
        }
        vis[vertex] = true;

        // 用已确定顶点松弛其余顶点的距离
        for (int nxt = 1; nxt <= n; nxt++) {
            if (graph[vertex][nxt] >= INF / 2) continue;
            const long long candidate = dist[vertex] + graph[vertex][nxt];
            dist[nxt] = min(dist[nxt], candidate);
        }
    }
    return dist[target];
}

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

    int n, m;
    cin >> n >> m;
    vector<vector<long long>> graph(n + 1, vector<long long>(n + 1, INF));
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        graph[a][b] = min(graph[a][b], w);
    }

    const long long ans = dijkstra(graph, 1, n);
    cout << (ans >= INF / 2 ? -1 : ans) << '\n';
    return 0;
}

复杂度分析​

读入为 O(m)；最多 n 轮中各做一次线性选点和一行扫描，时间为 O(n² + m)，通常记作 O(n²)；矩阵占 O(n²) 空间。

边界与易错点​

  • 只更新 graph[a][b]，不要把有向边误写成双向边。
  • 重边必须取最小值，不能直接覆盖。
  • 选点时排除已访问顶点，顺序是选点、标记、松弛。
  • 最终 dist[n] 仍为无穷大时输出 -1。

模式迁移​

当起点改变时，只替换 dist[source] = 0；若图稀疏，保留同一不变量，换成邻接表和最小堆选点。