Dijkstra 的运行时间分析，用于最短路径算法，但最大 K 停止

Question

对于这样的问题(https://leetcode.com/problems/cheapest-flights-within-k-stops/(，我可以用上限为 O(|E|+ |V|日志|V|(。

但是，由于存在最大 K 个停止的额外停止标准。如果 K <V，我的上限应该更小。>

问：如何将 K 停靠点合并到我对 Dijkstra 算法的分析中？

Q2：如果我们假设图形是完全连接的(每个顶点每隔一个顶点连接一次。所以 E = V^2(？这会改变分析吗？

Answer 1

Dijkstra的算法不适用于这个问题。 一旦它找到了通往顶点的最便宜的路径，它就不会寻找任何其他路径......但是，通往顶点的最便宜的路径可能会占用太多的插槽，以允许从那里到目标的最便宜的路径。 如果到达目标的站点留出更多可用站点，则通往中间顶点的更昂贵的路径可能是最好的路径。

例如：

S--1--A--1--B--1--C--1--T
          /          /
  `---4---'   `---9---'

在此示例中，从 S 到 T 且有 2 个停靠点的最便宜路径是成本为 6 的S-B-C-T路径。 但是 Dijkstra 的有限止损算法只能找到成本为 11 的S-A-B-T。

在我的头顶上，我知道的这个问题的最佳算法需要O(KE(时间。