索引优先级队列真的可以加快 dijkstra 的速度吗？
Do indexed priority queues actually speed up dijkstra?
“惰性”dijkstra 的最短路径算法具有 渐近 时间复杂度 O(Elog(V))，它使用常规优先级队列而不是索引堆。
这意味着算法将不得不跳过重复节点，但无论如何都要处理。
解决这个问题的方法是使用索引优先级队列，但我很困惑它是否真的比惰性版本更快，无论是在现实生活中还是在大 O 中，因为惰性版本仍然在很早的时候跳过重复节点算法。
通过一些研究，我还发现索引 dijkstra 的 space 复杂度 O(V) 比惰性实现的 O(E)，我不知道这是否会提高性能。
并没有降低理论上的渐近时间复杂度，仍然是O(ElogV)。
无论您是否实际插入或替换现有堆中的元素，它仍然需要 O(log|H|) 时间（其中 |H| 是堆的大小）。
在“lazy”版本中，|H|在O(|E|)中，在非“lazy”版本中，它在O(|V|)中，所以时间复杂度在O(|E|log|E|)中惰性版本，非惰性版本 O(|E|log|V|)。
但是由于|E|本身在O(|V|^2)中，并且由于log(|V|^2) =2log(|V|)，所以意味着O(|E|log|V|) = O(|E|log|E|)，渐近理论复杂度保持不变。
“惰性”dijkstra 的最短路径算法具有 渐近 时间复杂度 O(Elog(V))，它使用常规优先级队列而不是索引堆。 这意味着算法将不得不跳过重复节点，但无论如何都要处理。 解决这个问题的方法是使用索引优先级队列，但我很困惑它是否真的比惰性版本更快，无论是在现实生活中还是在大 O 中，因为惰性版本仍然在很早的时候跳过重复节点算法。 通过一些研究，我还发现索引 dijkstra 的 space 复杂度 O(V) 比惰性实现的 O(E)，我不知道这是否会提高性能。
并没有降低理论上的渐近时间复杂度，仍然是O(ElogV)。
无论您是否实际插入或替换现有堆中的元素，它仍然需要 O(log|H|) 时间（其中 |H| 是堆的大小）。
在“lazy”版本中，|H|在O(|E|)中，在非“lazy”版本中，它在O(|V|)中，所以时间复杂度在O(|E|log|E|)中惰性版本，非惰性版本 O(|E|log|V|)。
但是由于|E|本身在O(|V|^2)中，并且由于log(|V|^2) =2log(|V|)，所以意味着O(|E|log|V|) = O(|E|log|E|)，渐近理论复杂度保持不变。