修改后的 Dijkstra - 时间复杂度？

Question

我正在解决Leetcode问题787。 K 站内最便宜的航班.

基本上这是单源最短路径，但允许最多 k 个步骤。因此，我们不能使用普通的 Dijkstra 算法，如果我们已经到达成本较低的节点，我们就不会考虑路径。这里，成本较低的路径可能会耗尽到达目的地之前允许的 k 个步骤，我们可能必须采取成本较高的路径，但使用的步骤数较少。

我编写了普通 Dijkstra 算法的即兴编写来解决这个问题。这个解决方案已被接受，但我在确定它的时间复杂度时遇到了困难。

方法

在这种方法中，就像普通的 Dijkstra 一样，我将拉出成本最低的节点。但是在推送节点时，当成本或停止减少时我会推送。通过这种方式，最终将考虑可能具有更大成本但步骤更少的路径。

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // create adj list
        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

        // the below cost[i], stops[i], store the cost, stops for node i at some moment, these
        // are not necessarily the min cost , or lowest stops for node 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();

            // when we process the node, it is sure that cost of that node can't be improved,
            //  although it may be possible to reach node with lesser number of stops
            if(u == dst) 
                return ucost; 

            // we already used up k stops, can't go further
            if(ustops == k + 1)
                continue;
            
            for(auto &[v, edgecost] : adj[u])
            {
                // we found a better cost or better stops, we'll consider that path
                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;
    }
};

为此确定 TC 的问题是，a 节点可以多次推入最小堆 - 随着成本降低，我们更新成本并停止 |现在下次停靠点减少时，我们更新成本和停靠点（在此成本再次增加）|现在下次成本可以再次降低， 因此，我们不会采用任何降低成本或减少节点停靠点的固定模式。

有没有一种系统的方法可以分析上述方法的时间复杂度。

编辑 1：删除了多种方法，以使此问题集中于 1 种方法。

Answer 1

我无法提供严格的证明，只能提供直觉。

我们可以将问题重新表述为在修改后的图上运行原始 Dijkstra 算法，而不是考虑受约束的 Dijkstra 算法。对于原图中的顶点v_i（源顶点除外），我们可以将其分解为k顶点v_i, 1, v_i, 2 , …, v_i, k，每个都应该从源顶点到达，且不超过 1, 2, …, k 步。然后，对于原始图中连接 v_i 和 v_j 的边，连接 v_i、 l 和 v_{j 的边, l + 1}，对于所有 1 ≤ l < k 都添加到新图中。源顶点仍然只是新图中的一个顶点，但连接到与其原始邻居相对应的“1 步”顶点。现在，原来的问题相当于在新图上找到从源到与原始目标顶点对应的“k步”顶点的最短路径。

因此，您编写的修改后的 Dijkstra 算法实际上是在新图上运行的标准 Dijkstra 算法。因为新图大约有 k|E|边和 k|V|顶点，而标准 Dijkstra 的时间复杂度为 O(|E|log |V|)，而修改后的 Dijkstra 的时间复杂度确实为 O(k|E|log |V) |）正如用户24714692的评论中所指出的。

但是，我还没有提出严格的证明来证明运行修改后的 Dijkstra 与在原始图上运行标准 Dijkstra 是如何等效的。直观上，对于顶点 v_i，首先会发现使用 t 顶点（对于某些 t）的最短路径，然后使用 t − 1,  的最短路径是有意义的t − 2, t − 3, … 边（甚至可能不是 -1、-2 的步长，但可以是 -5、-8）。因此，代码中的 v_i 将充当 v_i, t, v_{i, t − 1}, v_{i , t − 2}, …在我上面构建的新图中，随着算法的运行。