邻接矩阵实现Dijkstra需用INT_MAX/2初始化图和dist数组，避免溢出和误判；visited全设false；小规模n下宜线性扫描选最小dist节点而非priority_queue；需路径时维护prev数组。
邻接矩阵存图时，dijkstra 的数组初始化怎么写才不出错
邻接矩阵实现 dijkstra 最容易在初始化阶段翻车：把未连接的边设为 0 或 -1，会导致算法误判为“存在一条长度为 0 的边”。必须用一个足够大的数（如 INT_MAX / 2）表示无穷大，且不能直接用 INT_MAX —— 后续松弛操作中 dist[u] + graph[u][v] 可能溢出。
-
graph[i][j]：若i到j无边，赋值为INT_MAX / 2；若有边，赋值为非负权值 -
dist[i]初始化为INT_MAX / 2，dist[src] = 0 -
visited[i]全部设为false
贪心选择的核心：每次选未访问节点中 dist 最小的，为什么不能用 priority_queue
邻接矩阵下，节点总数 n 通常不大（比如 ≤ 1000），而 priority_queue 带来的常数开销和额外内存反而不如线性扫描高效。更重要的是：邻接矩阵本身不支持快速获取某点的所有邻接边（得遍历整行），priority_queue 的优势无法发挥。
- 直接循环
for (int i = 0; i 找最小dist[i]且!visited[i]的点，时间复杂度O(n²)，简洁可控 - 若强行套用
priority_queue，需额外维护> dist更新同步问题（陈旧节点残留），反而易错 - 只有邻接表 + 稀疏图 + 大规模节点时，堆优化才真正有意义
dijkstra 松弛操作中，dist[u] + graph[u][v] 的边界检查不能省
即使你用了 INT_MAX / 2 初始化，仍可能因输入权值过大或图构造错误，导致 dist[u] + graph[u][v] 溢出变成负数，从而错误触发松弛。必须加防溢检查。
if (dist[u] != INT_MAX / 2 && graph[u][v] != INT_MAX / 2) {
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
}
}
- 两个条件缺一不可：
dist[u]不是无穷，说明u已可达；graph[u][v]不是无穷，说明边真实存在 - 漏掉任一判断，都可能让
INT_MAX / 2 + 正数溢出，结果小于dist[v]，引发错误更新 - 某些题目权值为 0，所以不能靠“是否 > 0”来判断边是否存在
路径还原不是必须的，但一旦需要，就得额外维护 prev 数组
dijkstra 本身只算最短距离，不记录路径。如果题目要求输出路径（比如打印从起点到终点的节点序列），必须在松弛成功时同步更新前驱节点。
立即学习“C++免费学习笔记（深入）”；
- 声明
vector，初始化全为 -1prev(n, -1) - 在
if (newDist 成立时，加一句prev[v] = u - 路径回溯用
while (v != -1) { path.push_back(v); v = prev[v]; }，再反转 - 注意：多个最短路时，
prev只保存其中一条（取决于松弛顺序），这不是 bug，是算法特性
0x3f3f3f3f，但在 C++ 标准库里它只是近似 1e9，遇到权值总和超 2e9 的题就会跪。老实用 INT_MAX / 2，配合显式溢出判断，比炫技重要得多。 
