使用邻接表和优先级队列的 Dijkstra 算法的时间复杂度是多少?

问题描述

假设我有这样的代码:

enqueue source vertex
while(queue is not empty){
    dequeue min vertex
    add to shortest path set
    iterate over vertex edges
        if not in shortest path set and new distance smaller enqueue 
}

如果 while 循环对图中的所有边运行而不是只对图中的所有顶点运行 V 次，时间复杂度是多少?还是 O(ELogV) 因为它是 O(E+E)*O(LogV)?

What is the time complexity if the while loop runs for all edges in the graph instead of only running V times, for all vertices in the graph? Is it still O(ELogV) since it's O(E+E)*O(LogV)?

推荐答案

是的，当您的优先级队列不支持 DECREASE_KEY 操作时，这几乎就是您实现 Dijkstra 算法的方式.优先级队列包含 (cost,vertex) 记录，每当您发现一个顶点成本低于前一个的顶点时，您只需插入一条新记录.

Yes, this is pretty much how you implement Dijkstra's algorithm when your priority queue doesn't support a DECREASE_KEY operation. The priority queue contains (cost,vertex) records, and whenever you find a vertex cost that is lower than the previous one, you just insert a new record.

复杂度变为O(E log E)，不大于O(E log V).

The complexity becomes O(E log E), which is no bigger than O(E log V).

当您使用确实支持 DECREASE_KEY 操作的二叉堆时，这与 Dijkstra 算法的复杂性相同，因为 DECREASE_KEY 需要 O(log V) 时间.为了得到 O(E + V log V)，您需要使用可以在恒定时间内执行 DECREASE_KEY 的斐波那契堆.

This is the same complexity that Dijkstra's algorithm has when you use a binary heap that does support the DECREASE_KEY operation, because DECREASE_KEY takes O(log V) time. To get down to O(E + V log V), you need to use a Fibonacci heap that can do DECREASE_KEY in constant time.

这篇关于使用邻接表和优先级队列的 Dijkstra 算法的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！