引入

Dijkstra 算法是求解单源最短路径的经典算法，适用于边权非负的图（有向或无向）。它从起点出发，逐步确定到各个节点的最短距离。

核心思想：贪心 + 松弛

  • 维护一个集合 S，表示已经确定最短距离的节点。

  • 初始时，起点到自己的距离为 0，到其他节点的距离设为无穷大（或 -1 表示不可达）。

  • 每次从未确定的节点中，选择一个当前距离最小的节点 u，将其加入 S。

  • 对 u 的所有出边 (u,v,w)进行松弛操作：
    如果 dist[u]+w<dist[v]，则更新 dist[v]=dist[u]+w。

  • 重复上述过程，直到所有节点都加入 S（或目标节点已确定）。

为什么贪心是正确的？

在非负权重的条件下，当从优先队列中取出距离最小的未确定节点 u 时，它的最短距离已经不可能再被其他节点更新了。
因为任何其他未确定节点的距离都 ≥dist[u]，而边权非负，所以经过它们到达 u 的距离只会 ≥dist[u]，不可能更短。因此 u 可以被安全地“固定”下来。

实现要点

  • 使用 dist[] 记录当前已知最短距离，vis[] 标记是否已确定。

  • 优先队列（小顶堆）存储 (距离, 节点)，方便快速取出最小距离节点。

  • 注意：同一个节点可能因多次松弛而被多次入队，所以出队时需要检查 vis[u]，若已确定则跳过。

适用与限制

  • ✅ 边权非负的有向/无向图。

  • ❌ 不能处理负权边：如果存在负权，贪心假设失效，可能得到错误结果。此时应使用 Bellman-Ford 或 SPFA。

  • 当所有边权相等（如均为 1）时，Dijkstra 退化为 BFS。

时间复杂度

  • 朴素实现（遍历所有节点找最小）：O(V2)，适合稠密图。

  • 堆优化（使用优先队列）：
    每个节点可能被多次入队，但每条边只会被松弛一次，总复杂度 O((V+E)log⁡V)，适合稀疏图。

模板题目：0蓝桥王国 - 蓝桥云课

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define maxn 300001

//边
struct Edge {
    ll v, w;
    Edge(ll _v, ll _w) : v(_v), w(_w) {}
};

//要放入堆中的值u、w，合并成一个节点
struct Node {
    ll u, w;
    Node(ll _u, ll _w) : u(_u), w(_w) {}
    //小顶堆，即 w 小的在前面
    bool operator<(Node b) const {
        return b.w < w;
    }
};

vector<Edge> edges[maxn];  //存图
vector<ll> ans(maxn, -1ll);//答案
bool vis[maxn];            //标记该节点的最短路是否已经找到

void dijkstra(int s) {
    //stl中代表堆的数据结构
    priority_queue<Node> que;
    //初始时加入第一个元素，作为起点
    ans[s] = 0;
    que.push(Node(s, 0));
    while (!que.empty()) {
        //每次取出在堆路径最短的点
        ll u = que.top().u;
        que.pop();
        //已经求出最短路径了，跳
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = 0; i < edges[u].size(); i++) {
            ll v = edges[u][i].v;
            ll w = edges[u][i].w;
            //发现如果从u到v的路径比原来的路径更短，进行一次松弛操作
            if (ans[v] == -1 || ans[v] > ans[u] + w) {
                ans[v] = ans[u] + w;
                //将v加入到堆里面去
                que.push(Node(v, ans[v]));
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        ll u, v, w;
        cin >> u >> v >> w;
        //注意是单向边
        edges[u].push_back(Edge(v, w));
    }
    dijkstra(1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
} 

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