Dijkstras算法的复杂度 [英] Complexity in Dijkstras algorithm

问题描述

因此，我一直在尝试分析我一直在研究的Dijkstras算法的特殊变体。我正在考虑最坏情况下的复杂性。

So I've been attempting to analyze a specialized variant of Dijkstras algorithm that I've been working on. I'm after the worst case complexity.

该算法使用斐波那契堆，在正常的Dijkstra情况下，该堆将以O（E + V log V）运行。

The algorithm uses a Fibonacci Heap which in the case of the normal Dijkstra would run in O(E + V log V).

但是，此实现需要在更新邻居的内部循环中进行查找。该查找将针对每个边执行，并且将以对数时间进行，其中查找位于包含所有边的数据结构中。此外，该图还具有以下限制：任何节点都不能有超过4个邻居。

However this implementation needs to do a lookup in the inner loop where we update neighbours. This lookup will execute for every edge and will be in logarithmic time, where the lookup is in a datastructure that contains all edges. Also the graph has the restriction that no node will have more than 4 neighbours.

O（V log V）是外循环的复杂度，但我我不确定内循环的最坏情况是什么。我在想，由于图形中的每个边都将被检查O（E）次，并且每个边都将需要对数时间，因此应该是E log E，它应超过V log V并得出O （E log E）算法的复杂性。

O(Vlog V) is the complexity for the outer loop but I'm not sure what the worst case will be for the inner loop. I'm thinking that since that each edge in the graph will be checked O(E) times and each edge will take logarithmic time it should be Elog E which should exceed Vlog V and result in O(Elog E) complexity for the algorithm.

任何见识都会很棒！

推荐答案

在斐波那契堆上，递减键的摊销复杂度为O（1），也就是说您有| E |。在斐波那契堆上进行此类操作，总成本为O（E）。你也有| V |提取最小操作，每个操作花费O（lnV）。因此总成本为O（E + VlnV）。

The amortized complexity of Decrease-Key on Fibonacci Heap is O(1), that is to say you have |E| such operations on the Fibonacci Heap, the total cost will be O(E). Also you have |V| Extract-Min operations, which cost O(lnV) each. So the total cost is O(E+VlnV).

这篇关于Dijkstras算法的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！