Dijkstra算法：优先队列与Set实现的时间复杂度对比及选型

一、两种实现代码 #

1. 使用Set实现 #

// V - 顶点总数
// S - 源节点
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});    // 时间复杂度O(logV)
    
    while (!s.empty())    // 恰好执行V次
    {
        auto top = *(s.begin());    // O(1)时间
        int dis = top.first;
        int node = top.second;
        s.erase(top);               // 均摊O(1)时间

        for (auto it: edge[node])    // 所有外层循环的该内层循环总执行次数为E（图的总边数）
        {
            int nb = it[0];
            int edge_weight = it[1];
            
            if (dist[nb] > dis + edge_weight)
            {
                s.erase({dist[nb], nb});    // O(logV)时间
                dist[nb] = dis + edge_weight;
                s.insert({dist[nb], nb});    // O(logV)时间
            }
        }
    }
}

2. 使用优先队列实现 #

// V - 顶点总数
// S - 源节点
vector<int> 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())    // 执行次数可能超过V次，记为堆的总元素数
    {
        int node = pq.top().second;    // O(1)时间
        pq.pop();                      // O(log(堆大小))时间
        
        for (int i=0; i<edge[node].size(); i++)    // 平均每个节点遍历(E/V)条边
        {
            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});    // O(log(堆大小))时间
            }
        }
    }
    return dist;
}

二、时间复杂度分析与疑问解答 #

Set实现的时间复杂度 #

Set中始终维护V个元素，外层循环执行V次，内层循环总执行次数为E。每次插入、删除Set元素的时间为O(logV)，因此总时间复杂度为O(VlogV + ElogV)，等价于O(ElogV)（当E≥V时，后者主导）。

疑问1：优先队列实现的时间复杂度与堆大小上界 #

优先队列版本中，同一节点可能因不同的距离值多次入堆，但由于Dijkstra算法仅处理非负权边，每个节点的最短路径确定后，后续入堆的该节点旧条目（距离更大）会被直接忽略（实际代码中可在弹出节点时判断当前距离是否等于dist[node]，若不等则跳过）。

堆的元素数量上界为O(E)：因为每条边最多触发一次松弛操作并将对应节点入堆一次（非负权边保证不会无限松弛）。每次入堆、出堆操作的时间为O(logE)，因此总时间复杂度为O(ElogE)。由于E≤V²（稠密图），logE=2logV，因此也可等价为O(ElogV)，但实际中优先队列的常数开销通常比Set更小。

疑问2：根据图类型选择实现方式及适用场景 #

• 稀疏图（E≈V）：优先队列实现更优。此时ElogE与ElogV的差距极小，但优先队列的push/pop操作常数远低于Set的插入/删除（Set需要维护有序性的额外开销），实际运行速度更快。
• 稠密图（E≈V²）：两种实现的时间复杂度均为O(V²logV)，但此时暴力Dijkstra算法（用数组维护距离，每次线性查找最小距离节点，时间O(V²)）会比这两种实现更高效。若必须在这两者中选择，Set实现的堆大小固定为V，而优先队列可能膨胀到O(V²)，此时Set的内存和时间表现更稳定。

另外，这两种实现仅适用于非负权边的图：Dijkstra算法的核心逻辑依赖“一旦节点被选出（从Set或堆中弹出），其最短路径已确定”的特性，负权边会破坏这一特性，导致计算结果错误。若需处理负权边，应使用Bellman-Ford或SPFA算法。

内容的提问来源于stack exchange，提问作者JavaLearner