基于堆的优先队列实现Dijkstra算法的时间复杂度疑问

你的误区在于对边的遍历次数理解有误，下面拆解核心逻辑：

1. 边的遍历总次数是m，而非n*m
   Dijkstra算法中，每次从堆取出节点u后，只会遍历u的所有邻接边，而非整个图的m条边。所有节点的邻接边总数正好是图的总边数m，所以整个算法过程中，边总共被遍历m次，不是n次循环每次都遍历m条边。

2. 松弛操作的总时间是O(m log n)
   每条边最多触发一次有效的松弛操作（当u被确定为最短路径的前驱时），每次松弛后若需要更新优先队列（比如将v的新距离入堆），操作耗时O(log n)，因此松弛操作的总时间是O(m log n)。

3. 堆的取出操作总时间是O(n log n)
   算法会执行n次堆顶取出操作（每个节点被取出一次），每次取出耗时O(log n)，总时间为O(n log n)。

4. 总时间复杂度合并
   将两部分时间相加：O(m log n + n log n)。对于连通图，m ≥ n-1，因此n log n项可以被m log n主导，最终时间复杂度简化为O(m log n)。

补充说明：如果实现中允许堆中存在同一节点的多个条目（旧的距离更大的条目），堆的总操作次数仍为O(m log n)（因为每条边最多插入一次），取出时遇到旧条目直接忽略，不影响整体复杂度。

内容的提问来源于stack exchange，提问作者Jaden 988