使用堆实现 Dijkstra
处理非负边上的贪心最短路径
使用堆实现 Dijkstra 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
最短路径问题
您希望求出从一个节点到其他每个节点的最低代价路径。每条边权重均为零或正数时，Dijkstra可以解决这个问题。
贪心思想
Dijkstra 采用贪心策略：它总是扩展已知距离最小的未访问节点，并相信这个距离已经确定。
为什么使用最小堆
要快速取出距离最近的节点，您需要一个最小堆。它能在 log n 时间内返回最小距离，而不必进行缓慢扫描。
import heapq从距离开始
将每个距离设为无穷大，然后将源点设为零。尚未到达的节点会一直保持无穷大。
dist = [float('inf')] * n
dist[src] = 0向堆中加入初始元素
将源点作为由（距离、节点）组成的元组压入堆中。将距离放在前面，堆就会自动按代价为各个条目排序。
pq = [(0, src)]弹出最近的节点
每轮循环都弹出最小的 (d, u)。这个 d 就是到 u 的最短距离，因此它弹出后就无需再处理。
d, u = heapq.heappop(pq)跳过过时条目
一个节点可能会以旧的、更大的距离留在堆中。当 d 大于已存储的距离时，请跳过这个条目。
if d > dist[u]:
continue松弛邻居
松弛是指尝试改进邻居：如果经过 u 更便宜，就更新它的距离并将它压入堆中。
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))延迟删除技巧
Python 的堆无法更新键，因此您可以压入重复条目，并忽略过时条目。这种惰性方式让代码简短而快速。
运行时间
使用二叉堆时，Dijkstra 的复杂度为O((V + E) log V)。它可以轻松处理包含数十万条边的图。
注意边权重
Dijkstra 遇到负权边时会失效，因为弹出的距离可能并不是最终结果。遇到这种情况，请改用 Bellman-Ford。
快速检查
您弹出了 (d, u)，但 d 大于 dist[u]。应该怎么做？
回顾：使用堆的 Dijkstra
您需要初始化距离，压入 (dist, node)，弹出距离最近的节点，跳过过时的弹出项，并松弛邻居。这就是复杂度为 O((V+E) log V) 的Dijkstra。🚀
常见问题解答
「使用堆实现 Dijkstra」课时是免费的吗？
是的 — 「使用堆实现 Dijkstra」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用堆实现 Dijkstra」这节课中我会学到什么？
处理非负边上的贪心最短路径 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「使用堆实现 Dijkstra」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 使用堆实现 Dijkstra
- 使用双端队列实现 0-1 BFS
- Bellman-Ford 与负权边
- Floyd-Warshall 全点对算法