索引优先队列是否真的能提升Dijkstra算法的运行效率？

基础实现差异 #

• 懒汉版Dijkstra采用普通优先队列而非索引堆实现，渐近时间复杂度为O(Elog(V))。算法运行过程中会出现重复的节点入队记录，即便这些记录最终弹出时会被直接跳过，仍需要额外的处理开销。
• 索引优先队列是解决重复入队问题的主流方案，公开资料显示该版本的空间复杂度为O(V)，优于懒汉版实现的O(E)。

待验证的性能疑问 #

• 时间复杂度量级上二者是否处于同一水平？索引优先队列版本的实际运行表现是否真的比懒汉版更高效？毕竟懒汉版可以在算法执行早期就直接跳过重复节点，没有队列元素更新的额外开销。
• 索引优先队列版本更优的空间复杂度，在实际运行场景中是否会带来可感知的性能提升？

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