Dijkstra算法邻接表最小堆与邻接矩阵普通数组队列性能对比疑问

理论层面的效率对比 #

• 邻接表 + 最小堆实现：时间复杂度为 O(M log N)，其中 M 为图的总边数，N 为总节点数。这类实现更适合边数远小于节点数平方的稀疏图场景。
• 邻接矩阵 + 数组暴力遍历找最小距离实现：时间复杂度为 O(N²)，耗时和边数无关，仅随节点数平方增长。这类实现更适合边数接近节点数平方的稠密图场景。

你的测试结果完全符合预期 #

出现你观察到的现象，核心原因有3个：

1. 500节点的场景下，N² 仅为25万，这个计算量级本身非常小，邻接矩阵版本的常数开销极低：直接通过数组下标寻址的访问延迟远小于堆操作的开销，最小堆的每次插入、弹出都需要做 O(logN) 级别的节点比较、交换，本身常数开销就比单纯的数组遍历高很多。
2. 你测试的应该是稠密图场景：当边数 M 接近 N² 时，M log N 的实际计算量会远大于 N²。比如N=500时，log₂(500)≈9，若边数接近25万，邻接表+堆版本的计算量约为225万，是邻接矩阵版本的9倍，后者运行更快是必然结果。
3. 如果你用的是没有做延迟删除的普通二叉堆实现，还会产生大量无效的堆节点操作，进一步拉高邻接表+堆版本的耗时，放大两者的速度差。

补充说明：你观察到的“初始阶段邻接表加最小堆运行更快”的现象也符合规律：初始测试应该是节点少、边数少的稀疏场景，此时M log N的计算量远小于N²，邻接表+堆的优势就能体现出来。

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