在图论计算中，带权重的最短路径求解是路由规划、地图导航等系统的核心。迪杰斯特拉算法作为单源最短路的经典解法，要求图中所有边权非负，通过贪心策略每次锁定当前距离最小的节点，再以其为起点松弛相邻边。下面以C++为例，从图存储到堆优化实现完整走一遍。
一、图结构与权重表示
带权图通常使用邻接表而非邻接矩阵，尤其在节点多、边稀疏的场景下更省内存。每个节点关联一个边列表，边记录目标节点与权重。C++中可用vector嵌套结构体实现，这样既保持缓存友好，也方便遍历。
定义边结构体时，建议把权重声明为int或long long，避免浮点误差影响比较。若业务需要浮点权，应使用double并小心精度。下面的代码展示了最简化的图定义方式，后续算法都基于该结构操作。
#include <vector>
#include <iostream>
using namespace std;
struct Edge {
int to; // 目标节点
int weight; // 边权重，必须非负
};
// 邻接表：graph[u] 存放从u出发的所有边
vector<vector<Edge>> graph;
二、朴素迪杰斯特拉与堆优化区别
朴素实现每次扫描所有节点找最小距离，时间复杂度O(V^2)，仅适合稠密图。实际工程多使用优先队列（最小堆）优化，把“取最小”交给堆，复杂度降为O((V+E)logV)。核心区别在于：堆中存的是“节点+当前距离”对，每次弹出堆顶即全局最小未确定节点。
需要注意的是，同一个节点可能因多次松弛而多次入堆，因此必须配合visited数组或在弹出时判断距离是否已过期。否则重复处理会让算法变慢甚至逻辑错误。下面的对比表列出两者关键差异：
| 实现方式 | 取最小节点 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素数组扫描 | 线性查找 | O(V^2) | 边密、V较小 |
| 优先队列优化 | 最小堆弹出 | O((V+E)logV) | 稀疏大图 |
三、C++堆优化实战代码
下面给出完整可编译的迪杰斯特拉实现。使用pair<int,int>存“距离,节点”，因priority_queue默认大顶堆，所以对距离取负或改用greater。代码先初始化距离为无穷大，源点距离置0并入堆，随后循环直至堆空。
松弛阶段遍历当前节点的所有出边，若新距离更小则更新并推入堆。visited数组在弹出时标记，保证每个节点只作为“确定最小”处理一次。该写法能稳妥应对节点重复入堆问题。
#include <vector>
#include <queue>
#include <climits>
#include <iostream>
using namespace std;
const int INF = INT_MAX;
// graph: 邻接表，n: 节点数，src: 源点
vector<int> dijkstra(const vector<vector<Edge>>& graph, int n, int src) {
vector<int> dist(n, INF);
vector<bool> visited(n, false);
// 小顶堆：存 (-距离, 节点) 或改用 greater
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) continue; // 过期条目跳过
visited[u] = true;
for (const Edge& e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
int main() {
int n = 5;
vector<vector<Edge>> g(n);
// 示例边：0-1权4，0-2权1，2-1权2，1-3权1，2-3权5，3-4权3
g[0].push_back({1, 4});
g[0].push_back({2, 1});
g[2].push_back({1, 2});
g[1].push_back({3, 1});
g[2].push_back({3, 5});
g[3].push_back({4, 3});
vector<int> d = dijkstra(g, n, 0);
for (int i = 0; i < n; i++) {
cout << "到节点 " << i << " 最短距离: " << d[i] << endl;
}
return 0;
}
四、负权边为何不可用
迪杰斯特拉依赖“已确定节点距离不再变更”的贪心前提。若存在负权边，可能从后续节点走出更短路径回头修正，但算法已标记该节点访问完成，于是得到错误结果。比如A到B权5，B到C权-4，A到C直连权2，朴素贪心会先锁C为2，却忽略A-B-C仅需1。
遇到负权场景应改用Bellman-Ford或SPFA。不过大多数实际业务如道路长度、传输延迟均为非负，因此迪杰斯特拉仍是首选。编码时可在建图阶段加断言防止误塞负权，提升调试效率。
提示：若需还原具体路径，可在松弛时额外记录pre数组，存前驱节点，结束后回溯即可。
五、工程化注意事项
在真实项目中，节点编号可能非连续或量级很大，可用unordered_map做映射。权重类型推荐统一用long long防溢出，特别是多段累加时。优先队列中存储距离建议用别名简化，例如using PII = pair<long long,int>。
另外，当图极稀疏且只需查单条路径时，A*算法结合启发式会更高效。但理解并写好基础迪杰斯特拉，是掌握一切最短路优化的根基。建议读者把上面代码跑通后，自行改为输出路径并测试不同图形。
Dijkstraweighted_graphC++修改时间：2026-08-03 08:12:29