Dijkstra 最短路CSP-S

💡 核心思想

Dijkstra 算法解决的是单源最短路径问题：给定一个边权非负的有向图（或无向图），求从源点 $s$ 到其他所有顶点的最短距离。核心思想：贪心地不断确认距离最近的未访问顶点的最短路。每一步从未确认的顶点中挑出距离最小的，标记为已确认，用它去松弛邻居。因为边权非负，已确认的顶点最短路不会再变短。

🎯 直觉理解

想象你从家出发找去所有地方的最短路。策略：先找离家最近的地方确认最短路，然后看经过已确认的地方能不能更快到达更远的地方。每次优先处理距离最小的未确认目的地。边权不能为负——否则已确认的最短路可能被"时光倒流路"推翻。

📝 算法流程

1. 初始化 dist[s]=0，其余 dist[v]=+∞
2. 将 $(0,s)$ 放入优先队列
3. 取出队首 $(d,u)$，若 $d > dist[u]$ 则跳过
4. 遍历出边：若 $dist[u]+w < dist[v]$ 则更新并压入队列
5. 结束后 dist[v] 即最短距离

$$dist[v] = \min(dist[v],\ dist[u] + w(u,v))$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const ll INF = 1e18;
struct Edge { int to; ll w; };
vector<ll> dijkstra(int n, const vector<vector<Edge>>& adj, int s) {
    vector<ll> d(n+1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    d[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist > d[u]) continue;
        for (auto& e : adj[u]) {
            ll nd = d[u] + e.w;
            if (nd < d[e.to]) { d[e.to] = nd; pq.push({d[e.to], e.to}); }
        }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, s; cin >> n >> m >> s;
    vector<vector<Edge>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    auto d = dijkstra(n, adj, s);
    for (int i = 1; i <= n; i++)
        cout << (d[i]==INF ? -1 : d[i]) << " 
"[i==n];
    return 0;
}

⚠️ 常见坑点

📚 相关题目