Dijkstra 是图论最短路的基础，但正因为太基础，很多选手反而对它一知半解。今天我整理了 5 个高频误区，帮你彻底避坑。
误区 1：Dijkstra 可以处理负权边
❌ 错误。Dijkstra 基于贪心策略，每次取 dist 最小的点进行松弛。一旦存在负权边，已经确定最短路的点可能会被更短的路径更新，导致答案错误。
✅ 正解：负权边请用 SPFA 或 Bellman-Ford。
误区 2：堆优化就是把所有点都 push 进堆
很多人习惯这么写：
for (int i = 1; i <= n; i++) pq.push({dist[i], i});❌ 这样既浪费空间，又增加了 log 复杂度。
✅ 正确的写法是 松弛成功时才入堆：
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}误区 3：Dijkstra 只能求单源最短路
其实它可以处理 多源最短路。我们只需要建立一个 超级源点，向所有起点连一条权值为 0 的边，然后跑一次 Dijkstra，求出的 dist 就是每个点到最近起点的距离。
误区 4：Dijkstra 不能求次短路
当然可以！我们维护两个数组 dist1（最短路）和 dist2（次短路）。每次松弛时，如果更新了最短路，就把原来的最短路“挤”给次短路。
误区 5：路径输出时直接存前驱
如果图中有多条最短路，只存一个前驱会丢失路径。建议在存前驱的同时记录 路径条数，或者使用 vector<int> pre[] 存储所有前驱节点。
最后提醒：写 Dijkstra 时，一定要注意
vis数组的标记时机——出队时标记，而不是入队时标记，否则会导致重复松弛。