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:
来自:www.hackerearth/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|)).