跳转至

K站中转内最便宜的航班

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

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

题解

Bellman-Ford算法

Bellman-Ford算法

来自https://drrany.github.io/ShortestPathAlgorithm/

Bellman-Ford 算法也是解决单源最短路径，其还可以处理有负边权的图。

首先要明确一点，在带有负边权的图中，不能有源点可达的负环，否则当从源点出发，将该负环循环走无数次，路径值会越来越小，也就不存在最短路径。所以当图中存在从源点可达的负环时，函数要返回 false。

思路：将图 G 中的所有边，遍历 n-1 次。对于边(u,v,w)，若dist[u]+w<dist[v]，则更新dist[v]。

  • 为什么要遍历所有边：第 i 次遍历，其实是确定其他点分别到源点的最短路径上，第 i 个顶点是谁，也可以说是经过的第 i 条边是谁。
  • 为什么要遍历 n-1 次：在每个顶点到源点的最短路径上，顶点数最多为 n 个，除非有负环，所以最多只需要遍历 n-1 次(第一个顶点已经确定下来了)，就可以确定所有顶点的最短路径。

本题用Bellman-Ford算法最自然也最简单：

class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        inf = float("inf")
        d = {node: inf for node in range(n)}
        d[src] = 0
        # 遍历中转次数
        for _ in range(k + 1):
            d_copy = d.copy()
            for s, t, v in flights:
                d_copy[t] = min(d_copy[t], d[s] + v)
            d = d_copy
        return d[dst] if d[dst] != inf else -1

这其实就是官方题解中的动态规划方法。

更简单的写法是一个二维dp数组：

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        f = [[float("inf")] * n for _ in range(k + 2)]
        f[0][src] = 0
        for t in range(1, k + 2):
            for j, i, cost in flights:
                f[t][i] = min(f[t][i], f[t - 1][j] + cost)

        ans = min(f[t][dst] for t in range(1, k + 2))
        return -1 if ans == float("inf") else ans

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/cheapest-flights-within-k-stops/solutions/954402/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-ha-abzi/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Dijsktra算法

当然，最短路问题依然可以用Dijsktra算法：

下面的代码来自评论区，学习一下

import collections
import heapq

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        if len(flights) == 0:
            return -1

        neibghbours = collections.defaultdict(list)
        for i, j, p in flights:
            neibghbours[i].append([j, p])

        # 检查起点和终点间是否有通路，没有则返回 -1
        visited = set()
        q = [src]
        while q:
            position = q.pop()
            visited.add(position)
            for nei, _ in neibghbours[position]:
                if nei not in visited:
                    q.append(nei)

        if dst not in visited:
            return -1

        # 用优先队列选择符合条件的最低价格
        pq = [[0, -1, src]] # 距离，中转次数，站点
        while pq:
            price, passed, position = heapq.heappop(pq)
            if position == dst:
                return price
            for nei_position, nei_price in neibghbours[position]:
                if passed + 1 <= k:
                    heapq.heappush(pq, [price+nei_price, passed+1, nei_position])

        return -1
最后更新: 2025-08-03 03:17:56
创建日期: 2025-08-03 03:17:56

广告

人要恰饭的嘛🤑🤑

评论