求「最多k次中转的最便宜航班」问题的最优时间复杂度算法

一、给定Java代码的时间复杂度分析 #

这段代码是基于队列的状态遍历算法，核心逻辑是跟踪「到达节点的花费、当前节点、已中转次数」这一状态，通过队列迭代更新最短路径。

时间复杂度拆解：

1. 邻接表构建：遍历所有航班（边），时间为O(E)，其中E是航班总数。
2. 队列处理：每个节点最多会以0~k共k+1种中转状态入队，每条边最多会被处理k+1次（对应每个节点的不同中转状态）。因此队列处理的总时间为O((k+1)*E)。

综合来看，整个算法的时间复杂度为O((k+1)*E)，简化后可记为O(k*E)。

二、是否存在更快的算法？ #

该问题的理论最优时间复杂度就是O(k*E)，不存在比这更快的算法——因为要找到最多k次中转的最短路径，必须遍历每条边最多k次，以覆盖所有可能的中转次数下的路径更新。

不过可以实现效率更优的同复杂度算法，比如Bellman-Ford的k次松弛优化版：

• 思路：用两个数组分别保存「上一轮中转次数的最短路径」和「当前轮次的最短路径」，对所有边执行k次松弛操作，每次迭代更新节点的最短路径。
• 优势：避免了队列的额外开销，也不会出现重复入队的冗余操作，实际运行效率通常优于给定的队列版算法。

另外，动态规划解法也能达到O(k*E)的时间复杂度，核心是定义dp[t][u]为经过t次中转到达节点u的最小花费，通过遍历边更新状态。

三、给定代码的逻辑说明 #

代码的核心流程：

• 初始化价格数组，起点节点的花费设为0，其余节点设为无穷大。
• 构建邻接表，存储每个出发节点对应的到达节点和航班价格。
• 使用队列存储状态元组(当前花费, 当前节点, 中转次数)，从起点状态开始迭代。
• 每次取出队列中的状态，若中转次数超过k则跳过；否则遍历当前节点的所有邻接节点，计算新的花费，若新花费比当前记录的更低，则更新价格并将新状态入队。

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