邻接矩阵版dijkstra适用于≤500顶点的稠密图，但n≥1000时因o(n²)时间与空间开销需换邻接表+堆；常见错误包括松弛条件漏判visited[v]、graphu≠inf及误用≥或int_max导致溢出。
邻接矩阵实现的 Dijkstra 算法在小规模稠密图（顶点数 ≤ 500）中直接、稳定、不易出错；但一旦顶点数上到 1000+，O(n²) 时间开销和 O(n²) 内存占用会迅速成为瓶颈——别硬扛，该换邻接表+堆就换。
为什么邻接矩阵版 Dijkstra 容易写错 dist 更新逻辑
常见错误是把「松弛操作」写成单向覆盖，漏掉条件判断。核心不是“只要更小就赋值”，而是“仅当通过当前最短点 u 能让 v 更近时才更新”。否则会把不可达点误判为可达，或提前固化错误距离。
关键检查点：
-
dist[v] > dist[u] + graph[u][v]必须严格大于，不能写成>=或漏掉graph[u][v] != INF判断 -
visited[v] == false必须参与判断，否则可能用已确定的点反复更新，破坏贪心性质 - 初始化时所有非直连边必须设为一个真正意义上的“无穷大”，比如
INT_MAX / 2，而非INT_MAX—— 否则dist[u] + graph[u][v]可能溢出变成负数
邻接矩阵版 Dijkstra 的标准 C++ 实现模板
以下是最简可用、无依赖、可直接粘贴编译的版本（假设顶点编号从 0 开始，n 为顶点总数）：
void dijkstra(int start, int n, const vector<vector>>& graph, vector<int>& dist) {
vector<bool> visited(n, false);
dist.assign(n, INT_MAX / 2);
dist[start] = 0;
for (int i = 0; i dist[u] + graph[u][v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
</bool></int></vector>
注意：graph[u][v] 存储的是边权，无边时必须填 INT_MAX / 2（或其他安全哨兵值），不能用 -1 或 0 表示不存在——那会和真实零权边冲突。
什么时候必须放弃邻接矩阵改用邻接表+priority_queue
三个明确信号出现任一，就该重构：
- 输入图的边数
m远小于n²（例如n = 5000，但m ≈ 10000），此时邻接矩阵浪费 25MB 内存且遍历效率极低 - 运行时发现单次最短路计算耗时超过 200ms（在现代 CPU 上），尤其重复调用时
- 需要支持动态加边或多次查询不同起点——邻接矩阵版每次都要重跑，而堆优化版可复用结构
邻接表+priority_queue 的核心差异只在两处：用 vector<vector int>>></vector> 存图，以及用 priority_queue<pair int>, vector<...>, greater<...>></...></...></pair> 替代内层循环找最小值。其余逻辑完全一致。
邻接矩阵版最隐蔽的坑不在算法本身，而在图数据加载阶段：读入边时若没把对称边（无向图）或反向边（有向图）补全，或把 INF 值误设为 0，后续所有 dist 都会错得毫无征兆。动手前先打印两三行 graph 矩阵验证，比调试半小时强得多。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
