K 站中转内最便宜的航班

标签: 深度优先搜索 广度优先搜索 图 动态规划 最短路 堆（优先队列）

难度: Medium

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下


从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下


从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 104
  • 航班没有重复，且不存在自环
  • 0 <= src, dst, k < n
  • src != dst

Submission

运行时间: 27 ms

内存: 17.4 MB

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        pre = [float('inf')] * n
        pre[src] = 0
        cur = pre[:]
        rang = [[] for _ in range(n)]
        for u, v, d in flights:
            rang[u].append((v,d))
        q = deque([src])
        for i in range(k+1):
            for i in range(len(q)):
                u = q.popleft()
                for v, d in rang[u]:
                    if pre[u] + d < cur[v]:
                        cur[v] = pre[u] + d
                        q.append(v)
            pre = cur[:]
        return -1 if cur[dst] == float('inf') else cur[dst]

Explain

这个题解使用了最短路径的 Bellman-Ford 算法的思路。它通过动态规划的方式，在有限的中转次数内，逐步松弛图中的每条边，最终得到从起点到终点的最短路径。具体来说，使用两个数组 pre 和 cur 分别记录上一轮松弛后和当前正在松弛的每个点的最短距离。每一轮松弛时，都利用 BFS 的方式遍历当前能够到达的所有点，用 pre 数组的信息更新 cur 数组，并将所有被更新的点加入队列。当遍历完 k+1 轮后，cur[dst] 即为从 src 到 dst 的最短路径。

时间复杂度: 平均 O(ke)，最坏 O(n^3)

空间复杂度: O(n+e)

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        # 初始化 pre 和 cur 数组，pre 记录上一轮松弛后的最短距离
        pre = [float('inf')] * n
        pre[src] = 0
        cur = pre[:]
        
        # 邻接表 rang 存储每个点可以到达的边
        rang = [[] for _ in range(n)]
        for u, v, d in flights:
            rang[u].append((v,d))
        
        # 初始化 BFS 队列，首先只包含起点 src    
        q = deque([src])
        
        # 执行 k+1 轮松弛
        for i in range(k+1):
            # BFS 遍历当前队列中的所有节点
            for i in range(len(q)):
                u = q.popleft()
                # 遍历节点 u 的所有出边 (v,d)
                for v, d in rang[u]:
                    # 如果经过 u 到达 v 的距离更短，则松弛该边
                    if pre[u] + d < cur[v]:
                        cur[v] = pre[u] + d
                        q.append(v)
            # 本轮松弛完成后，将 cur 数组复制给 pre 数组                
            pre = cur[:]
        
        # 如果到达终点的距离仍为 inf，则不存在最短路径，返回 -1
        # 否则返回最短距离 cur[dst]
        return -1 if cur[dst] == float('inf') else cur[dst]

Explore

题解中结合了Bellman-Ford算法和BFS的思路，这种方法并不是传统的Bellman-Ford算法的标准实现。传统的Bellman-Ford算法会对所有边进行松弛操作，而这里使用BFS是为了优化性能，只对可能改进距离的边进行松弛。这种方法减少了不必要的松弛操作，尤其是在稀疏图中，可以大幅减少计算量。但这种方法的缺点是需要维护一个队列，并且在实现上比标准的Bellman-Ford算法复杂。

在每一轮松弛操作中，将当前队列中所有节点遍历一遍是为了确保所有可能被更新的节点都得到处理。这种做法可以理解为一种优化，它减少了不必要的边的检查，因为只有那些在前一轮中已经更新了距离的节点才可能导致新的松弛。这与传统的Bellman-Ford算法不同，后者在每轮中会检查所有的边，不论它们的起点节点在前一轮是否有更新，这使得传统方法在某些情况下效率较低。

如果到达终点的距离仍为inf，这通常意味着在给定的中转次数k内，不存在从起点到终点的路径。确实，如果k设置得太小，可能无法足够地松弛边来找到从起点到终点的有效路径。此外，如果图中存在不可达的顶点或者起点和终点之间的实际路径需要的中转次数超过k，也会出现这种情况。

使用两个数组pre和cur来记录不同阶段的最短路径可以防止在一轮松弛过程中新计算的值影响同轮的其他松弛操作，从而确保每轮松弛操作都基于同一轮次的数据进行。这种方法的优势是可以避免数据污染，使算法的逻辑更清晰，易于理解和调试。然而，其劣势是空间复杂度增加，因为需要额外的数组来存储变量的历史状态，这会导致更高的内存消耗。