我使用的是邻接矩阵,优先级队列是数据结构.
根据我的计算,复杂度为V ^ 3 log V：
> while循环：V
>检查相邻的顶点：V
>如果条目已存在,则检查队列,并更新相同的内容：V log v
但是,我到处都读到复杂性是V ^ 2
请解释.
解决方法
如果您使用Fibonacci堆,则提取min是O(lg V)摊销成本并更新其中的条目是O(1)摊销.
如果我们使用这个伪代码
while priorityQueue not empty
u = priorityQueue.exractMin()
for each v in u.adjacencies
if priorityQueue.contains(v) and needsWeightReduction(u,v)
priorityQueue.updateKeyWeight(u,v)
假设该实现具有priorityQueue.contains(v)和needsWeightReduction(u,v)的恒定时间.
需要注意的是,您可以稍微加强检查邻接关系.虽然外循环运行V次,并且检查任何单个节点的邻接是最坏的V操作,但是您可以使用聚合分析来实现您永远不会检查超过E邻接(因为只有E边缘).并且E< = V ^ 2,所以这是稍微好一点的界限. 所以,你有外循环V次,内循环E次.提取min运行V次,并且更新堆中的条目运行E次.
V*lgV + E*1 = O(V lgV + E)
同样,由于E< = V ^ 2,你可以用这个事实来代替和得到
O(V lgV + V^2) = O(V^2)
但在考虑稀疏图时,这是一个更宽松的界限(尽管是正确的).
