考虑dijkstra算法的以下两个实现：

使用set：

// V - total number of vertices
// S - source node
void dijkstra(int V, vector<vector<int>> edge[], int S)
{
    vector<int> dist(V, 1e9);
    dist[S] = 0;
    
    set<pair<int, int>> s;
    for (int  i=0; i<V; i++)
        s.insert({dist[i], i});    // log(V) time
    
    while (!s.empty())    // exactly V times
    {
        auto top = *(s.begin());    // constant time
        int dis = top.first;
        int node = top.second;
        s.erase(top);               // amortised constant time

        for (auto it: edge[node])    // For all the iterations of outer while loop this will sum up to E, where E is the total number of edges in the graph
        {
            int nb = it[0];
            int edge_weight = it[1];
            
            if (dist[nb] > dis + edge_weight)
            {
                s.erase({dist[nb], nb});    // log(V) time
                dist[nb] = dis + edge_weight;
                s.insert({dist[nb], nb});    // log(V) time
            }
        }
    }
}

使用优先级队列：

// V - total number of vertices
// S - source node
void dijkstra(int V, vector<vector<int>> edge[], int S)
{
    vector<int> dist(V, 1e9);
    dist[S] = 0;
    
    priority_queue<pair<int, int> , vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({dist[S], S});
    
    while (!pq.empty())    // Can be more than V times, let's call this heap_size times
    {
        int node = pq.top().second;    // O(1) time
        pq.pop();                      // log(heap_size) time
        
        for (int i=0; i<edge[node].size(); i++)    // Can be approximated to (E/V), where E is the total number of edges in the graph
        {
            int nb = edge[node][i][0];
            int edge_weight = edge[node][i][1];

            if (dist[nb] > dist[node] + edge_weight) {
                dist[nb] = dist[node] + edge_weight;
                pq.push({dist[nb], nb});    // log(heap_size) time
            }
        }
    }
    return dist;
}

使用基于集合的方法找到时间复杂度很容易，因为集合中元素的数量正好是V（顶点数），并且每个边都运行内部for循环，因此它的时间复杂度是O（V*log（V）V E*log（V）），相当于O（E*log（V））（原因：Dijkstra算法的时间复杂度是多少）

但是我很难理解priority_queue方法的时间复杂度。这里同一个节点可以在不同距离的priority_queue中多次出现。如何计算添加到堆中的节点数量的上限？

我还想根据图的性质（稀疏vs密集）来决定使用哪个实现，这两种实现对于任何类型的图都是等价的吗？