改进版Dijkstra算法求解Leetcode787的时间复杂度分析

问题背景 #

这是带最多k站限制的单源最短路径问题。普通Dijkstra算法会忽略已找到更低代价的路径，但此处低代价路径可能耗尽允许的步数，因此需采用改进版Dijkstra：当节点的代价更低或者步数更少时，将其加入最小堆。该方案已通过测试，但节点可能多次入堆，代价和步数的变化无固定递减模式，需要系统的时间复杂度分析方法。

实现代码 #

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // 创建邻接表
        vector<vector<pair<int, int>>> adj(n); //u -> {v, w}
        for(int i = 0; i < flights.size(); i++)
        {
            adj[flights[i][0]].push_back({flights[i][1], flights[i][2]});
        }

        // 改进版Dijkstra
        // cost[i], stops[i] 存储节点i当前记录的代价和步数，并非一定是全局最小代价或最少步数
        vector<int> cost(n, INT_MAX);  
        vector<int> stops(n, INT_MAX); 
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> minheap;
        cost[src] = 0;
        stops[src] = 0;
        minheap.push({cost[src], src, stops[src]});
        while(!minheap.empty())
        {
            auto [ucost, u, ustops] = minheap.top();
            minheap.pop();

            // 首次弹出目标节点时，其代价即为最小代价（堆的性质保证）
            if(u == dst) 
                return ucost; 

            // 已用完允许的最大步数，无法继续扩展
            if(ustops == k + 1)
                continue;
            
            for(auto &[v, edgecost] : adj[u])
            {
                // 找到代价更低或步数更少的路径时，更新并加入堆
                if(cost[v] > ucost + edgecost || stops[v] > ustops + 1)
                {
                    cost[v] = ucost + edgecost;
                    stops[v] = ustops + 1;
                    minheap.push({cost[v], v, stops[v]});
                }

            }
        }
        return -1;
    }
};

时间复杂度系统分析方法 #

要分析这种改进版Dijkstra的时间复杂度，核心是统计每个节点可能入堆的次数上限，再结合堆操作的时间成本：

1. 节点入堆次数的上限约束 #

每个节点v的入堆次数由两个维度限制：

• 步数维度：允许的最大步数是k+1次（k站对应k+1条边），所以每个节点的步数只能从0到k+1，共k+2种可能的步数状态。
• 代价维度：对于每个固定的步数s（0 ≤ s ≤ k+1），节点v在步数s下的代价只会单调递减。因为题目中航班价格（边权）都是正数，同一步数下后续找到的路径代价不可能比之前更新的更小，所以每个步数状态下节点最多入堆一次。

因此，每个节点最多会被入堆k+2次。

2. 总堆操作次数与时间成本 #

假设图中有n个节点，m条边：

• 总入堆次数最多为n*(k+2)次。
• 每次堆的插入和弹出操作的时间复杂度是O(log(n*(k+2)))，近似为O(log(nk))（当k远小于n时可简化为O(log n)）。
• 每条边最多会被遍历k+2次（每个出发节点的每个步数状态对应一次遍历），遍历边的总时间是O(m*(k+2))。

3. 最终时间复杂度 #

综合起来，该算法的时间复杂度为：
O((n + m)*(k+2)*log(n*(k+2)))，或者简化为O((n + m)*k*log(nk))（当k≥1时）。

关键验证点 #

• 同一步数下节点只会入堆一次：因为边权为正，当节点v在步数s下被更新为代价c后，后续任何到达v且步数为s的路径代价都不可能比c更小，不会再触发同一步数下的入堆操作。
• 步数的上限k+2是严格的：每个节点的步数不可能超过k+1（否则会被跳过），所以每个节点的步数状态只有0到k+1这k+2种可能。

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