Dijkstra 时间复杂度与 C++ pq

Question

二叉堆的 Dijkstra 时间复杂度为 O(V+ElogV)。

但是，C++ pq（如果用作二进制堆）不支持减少键。建议的一种解决方案是在 pq 中再次插入相同的顶点，并减少距离。例如：

发件人：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).

我说的对吗？如果不是，正确的复杂度应该是多少？

Answer 1

对于简单的连通图，这些界限实际上是等价的。自

|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|)).

Dijkstra 时间复杂度与 C++ pq

Dijkstra time complexity with C++ pq

algorithm

graph

dijkstra