使用 C++ pq 的 Dijkstra 时间复杂度 [英] Dijkstra time complexity with C++ pq

问题描述

Dijkstra 时间复杂度是 O(V+ElogV) 与二进制堆.

Dijkstra time complexity is O(V+ElogV) with binary heaps.

但是，C++ pq(如果用作二叉堆)，不支持减少键.建议的一种解决方案是在 pq 中再次插入相同的顶点并减少距离.例如:

But, C++ pq(if used as binary heap), does not support decrease key. One solution suggested is to just insert the same vertex again in pq with decreased distance. For, ex:

来自:https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/

void dijkstra(){
                                                // set the vertices distances as infinity
    memset(vis, false , sizeof vis);            // set all vertex as unvisited
    dist[1] = 0;
    multiset < pair < int , int > > s;          // multiset do the job as a min-priority queue

    s.insert({0 , 1});                          // insert the source node with distance = 0

    while(!s.empty()){

        pair <int , int> p = *s.begin();        // pop the vertex with the minimum distance
        s.erase(s.begin());

        int x = p.s; int wei = p.f;
        if( vis[x] ) continue;                  // check if the popped vertex is visited before
         vis[x] = true;

        for(int i = 0; i < v[x].size(); i++){
            int e = v[x][i].f; int w = v[x][i].s;
            if(dist[x] + w < dist[e]  ){            // check if the next vertex distance could be minimized
                dist[e] = dist[x] + w;
                s.insert({dist[e],  e} );           // insert the next vertex with the updated distance
            }
        }
    }
}

这种实现的复杂性应该会增加(与文章中声称的相反，O(V+ElogV))，因为堆的大小>V.我认为复杂度应该是 O(V+ElogE).

The complexity should increase with this implementation(as opposed to claimed in the article, O(V+ElogV)), as the heap is size>V. I believe the complexity should be O(V+ElogE).

我说得对吗?如果不是，那么正确的复杂度应该是多少?

Am I correct? If not, what should be correct complexity?

推荐答案

对于简单的连通图，这些边界实际上是等价的.由于

Those bounds are actually equivalent for simple connected graphs. Since

|V| − 1 ≤ |E| ≤ |V| (|V| − 1)/2,

我们可以通过日志发现

log(|V|) − O(1/|V|) ≤ log(|V| − 1) ≤ log(|E|) ≤ log (|V| (|V| − 1)/2) ≤ 2 log(|V|),

因此 Θ(log(|V|)) = Θ(log(|E|)).

hence Θ(log(|V|)) = Θ(log(|E|)).

这篇关于使用 C++ pq 的 Dijkstra 时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！