经典的图论问题

MrHe··6 min read

K 站中转内最便宜的航班 (LeetCode 787)

问题描述

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [from_i, to_i, price_i] ，表示该航班将会从城市 from_i 前往 to_i ，价格为 price_i 。

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

示例 1：

  • 输入: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1

  • 输出: 200

  • 解释: 从城市 0 到城市 2 的最便宜的路径是 0 -> 1 -> 2，价格为 100 + 100 = 200。 另一条路径是 0 -> 2，价格为 500。但这条路是直飞，中转次数为0，也符合最多1次中转的要求。但 200 更便宜。

示例 2：

  • 输入: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0

  • 输出: 500

  • 解释: 从城市 0 到城市 2 最便宜的路径是 0 -> 2，这条路径没有中转，符合最多0次中转的要求。

拿到这个题，第一反应是啥？图，最短路径。但是，它加了一个限制：最多 K 次中转。这个 K 就是整个问题的灵魂。如果没有这个 K，那就是一个标准的 Dijkstra 或者 Bellman-Ford 问题。但有了 K，事情就变得有意思了。

这意味着我们不仅要关心路径的总成本，还要关心路径的“长度”，也就是经过的站点数。

好，老规矩，咱们从最暴力的方法想起。

解法一：暴力搜索 (DFS)

最无脑的办法是啥？就是把所有从 src 出发，在 K 次中转内能到 dst 的路径都找出来，然后取个最小值。这不就是深度优先搜索（DFS）的思路吗？

我的递归函数应该长什么样？ 我需要知道当前在哪(curCity)，还剩下多少次中转次数(remainingStops)。

  • 递归函数定义：dfs(curCity, remainingStops, currentCost)

  • Base Case:

    1. 如果 currentCost 已经比我找到的全局最小成本 minCost 还大了，那就没必要再往下走了，直接剪枝返回。

    2. 如果 curCity 就是 dst，说明找到了一条路，更新 minCost = min(minCost, currentCost)，然后返回。

    3. 如果 remainingStops < 0，说明中转次数用完了还没到终点，这条路废了，返回。

  • 递归过程： 遍历 curCity 的所有邻居 nextCity，然后递归调用 dfs(nextCity, remainingStops - 1, currentCost + price)。

为了方便查找一个城市的所有出边，我得先预处理一下 flights 数组，建成一个邻接表。

import java.util.*;

class Solution1 {
    private Map<Integer, List<int[]>> graph = new HashMap<>();
    private int minCost = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 构建邻接表: key=出发城市, value=List<[到达城市, 价格]>
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], v -> new ArrayList<>()).add(new int[]{flight[1], flight[2]});
        }

        // k次中转意味着最多可以乘坐 k+1 次航班
        dfs(src, dst, k + 1, 0);

        return minCost == Integer.MAX_VALUE ? -1 : minCost;
    }

    private void dfs(int currentCity, int dst, int flightsLeft, int currentCost) {
        // 剪枝：如果当前花费已经超过了已知的最小花费，就没必要继续了
        if (currentCost >= minCost) {
            return;
        }

        // 找到了目的地
        if (currentCity == dst) {
            minCost = currentCost;
            return;
        }

        // 航班次数用完了
        if (flightsLeft == 0) {
            return;
        }

        // 遍历所有可达的下一个城市
        if (graph.containsKey(currentCity)) {
            for (int[] next : graph.get(currentCity)) {
                int nextCity = next[0];
                int price = next[1];
                dfs(nextCity, dst, flightsLeft - 1, currentCost + price);
            }
        }
    }
}

这个思路很简单很直接，但问题也很大。如果图的结构复杂，路径非常多，它会尝试几乎所有可能的路径，时间复杂度是指数级的。提交上去，大概率就是“Time Limit Exceeded”。暴力解法是咱们思考的起点，不是终点。

解法二：广度优先搜索 (BFS - 队列式分支限界法)

DFS 是一条路走到黑，很容易在某条很深的错误路径上浪费时间。那我们能不能换个思路？能不能一层一层地来？

这里的“层”是什么？就是航班的次数（或者说中转次数）。

  • 第 0 层：从 src 出发，经过 0 次中转（直飞）能到的地方。

  • 第 1 层：从 src 出发，经过 1 次中转能到的地方。

  • ...

  • 第 K 层：从 src 出发，经过 K 次中转能到的地方。

这不就是 BFS 的思路吗？我们用一个队列来辅助。队列里存什么呢？不能只存城市了，还得存到这个城市的当前状态，包括 [当前城市, 到达该城市的成本]。

  • 算法流程:

    1. 用一个 minCosts 数组记录到达每个城市的最小花费，初始化为无穷大。

    2. 初始化队列，把 [src, 0] (到达src成本为0) 放进去。

    3. 我们总共可以飞 k+1 次，所以我们进行 k+1 轮 BFS。

    4. 在每一轮循环中，处理当前队列里的所有节点。注意，是 当前队列里的所有节点，处理完才算一层结束。

    5. 从队列中取出一个状态 [curCity, curCost]，遍历它的所有邻居 nextCity。

    6. 计算新的成本 newCost = curCost + price。

    7. 如果 newCost 比已记录的到达 nextCity 的最小花费 minCosts[nextCity] 还要小，那么更新 minCosts[nextCity]，并把 [nextCity, newCost] 加入队列，供下一轮使用。

    8. k+1 轮结束后，minCosts[dst] 就是答案。

这个方法其实就是 队列式分支限界法 的一种体现。每一层（每一次中转）都是一个扩展阶段，我们只保留每一层中到达相同城市的最优（最便宜）的路径，剪掉了那些同样到达该城市但花费更高的 "分支"。

import java.util.*;

class Solution2 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 构建邻接表
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], v -> new ArrayList<>()).add(new int[]{flight[1], flight[2]});
        }

        // costs[i] 存储从 src 到达城市 i 的最低花费
        int[] costs = new int[n];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[src] = 0;

        // 队列存储 [当前城市, 到达该城市的当前花费]
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{src, 0});

        int stops = 0;
        // 最多 k 次中转，意味着最多可以乘坐 k+1 次航班
        while (!queue.isEmpty() && stops <= k) {
            int size = queue.size();
            // 必须用一个临时数组来存储这一层的更新，避免在同一层内互相影响
            // 比如 A->B, A->C，在同一层处理时，B可能会影响到C的结果，这是不对的
            // 稍后我们看第三种解法会发现，Bellman-Ford的思想完美解决了这个问题
            // 这里为了保持BFS的层次性，我们还是按层处理。
            // 但有个更简单的实现，我们只需要一个costs数组就够了
            // 每一轮循环都用上一轮的costs结果来更新，这样天然保证了层次。
            // 我们直接看那种DP/Bellman-Ford的实现，会更清晰。

            // 为了体现纯BFS，我们还是按层来
            // 这个级别内的更新不能影响本级别其他节点的计算
            int[] currentLevelCosts = Arrays.copyOf(costs, n);

            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int u = current[0];
                int cost_u = current[1];

                if (!graph.containsKey(u)) continue;

                for (int[] neighbor : graph.get(u)) {
                    int v = neighbor[0];
                    int price_uv = neighbor[1];

                    if (cost_u + price_uv < currentLevelCosts[v]) {
                        currentLevelCosts[v] = cost_u + price_uv;
                        queue.offer(new int[]{v, currentLevelCosts[v]});
                    }
                }
            }
            costs = currentLevelCosts; // 将本层的计算结果更新为全局结果
            stops++;
        }

        return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
    }
}

注意：上面的BFS实现有点问题， queue.offer(new int[]{v, currentLevelCosts[v]}) 时，如果一个节点被多次更新，会被多次入队，这会导致重复计算。BFS的层级性在这里是通过 stops 变量控制的。但这种带权重的图，纯粹的按层级BFS并不完美，引出了我们的下一种方法。

解法三：Dijkstra 算法的变种 (优先队列式分支限界法)

BFS 是公平地对待每一层的每一个节点。但是，同样是飞了2次，一条路可能花了200块，另一条路花了800块。我们是不是应该优先从那条只花了200块的路继续往下探索？

这种“优先探索成本最低的”不就是 Dijkstra 算法的核心思想吗？

标准的 Dijkstra 算法用一个优先队列（小顶堆）来存 [城市, 从源点到此城市的成本]，每次都弹出成本最低的节点去扩展。但它有个问题：一旦一个节点被处理过（从优先队列中弹出），就不会再处理它了。因为 Dijkstra 的贪心策略能成立的前提是：第一次到达一个节点时的路径一定是最短的。但在我们这个问题里，这不成立！

为什么？因为有 K 的限制。可能我第一次花 200 块飞了 3 次到达了城市 A，但后来又发现一条路，花了 300 块但只飞了 1 次就到了城市 A。虽然 300 > 200，但这条路更“短”（航班次数少），它还有更多的中转机会去到终点，它可能是一条更优解的“前缀”。

所以，我们需要改造 Dijkstra。状态里不能只有城市和成本，还得加上中转次数。

  • 优先队列中存储: int[] {cost, city, stopsLeft}， 按照 cost 升序排列。

  • 算法流程:

    1. 初始化优先队列，放入 [0, src, k+1] (成本0，在src城，还剩k+1次航班)。

    2. 需要一个二维数组 minStops[city][stops] 或者一个Map<Integer, Integer> minStops 记录到达某个城市 city 时，剩余 stops 次数时的最小花费。或者，更简单地，我们用一个数组 minFlightsToCity[city] 记录到达 city 所需的最小航班数。

    3. 当从队列中取出 [cost, u, flights] 时:

      • 如果 u 是 dst，直接返回 cost。因为优先队列的性质，第一个到达 dst 的一定是最便宜的。

      • 如果 flights > 0，遍历 u 的邻居 v：

        • 计算新成本 newCost = cost + price_uv。

        • 将 [newCost, v, flights - 1] 加入优先队列。

    4. 为了剪枝，我们可以记录到达每个城市时所用的最少航班次数。如果当前路径到达city时用的航班次数比之前记录的还多，且cost还高，那肯定不是最优的，可以剪掉。

看代码：

import java.util.*;

class Solution3 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // 构建邻接表
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], v -> new ArrayList<>()).add(new int[]{flight[1], flight[2]});
        }

        // 优先队列：[cost, city, stops_left]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, src, k + 1});

        // 记录到达每个城市时，还剩下多少站可以飞。用于剪枝。
        // stops[i] 表示到达城市 i 时，剩余的最大可用航班数
        int[] stops = new int[n];
        Arrays.fill(stops, -1);

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int cost = current[0];
            int city = current[1];
            int flightsLeft = current[2];

            // 如果当前节点剩余的航班数比之前记录的还少，说明不是更优路径，跳过
            if (flightsLeft < stops[city]) {
                continue;
            }
            stops[city] = flightsLeft;

            if (city == dst) {
                return cost;
            }

            if (flightsLeft > 0 && graph.containsKey(city)) {
                for (int[] neighbor : graph.get(city)) {
                    int nextCity = neighbor[0];
                    int price = neighbor[1];
                    pq.offer(new int[]{cost + price, nextCity, flightsLeft - 1});
                }
            }
        }

        return -1;
    }
}

这个解法就是 优先队列式分支限界法 的完美体现。优先队列帮助我们总是沿着当前看起来“最有希望”（成本最低）的分支进行探索，从而更快地找到最优解。

解法四：动态规划 (Bellman-Ford 思想)

最后我们换一个角度，从动态规划（DP）来思考。

K 次中转，这个 K 很像 DP 状态中的一维。

  • 定义状态: dp[i][j] 表示经过 i 次航班后，到达城市 j 的最小花费。

  • 初始化: dp 数组所有值设为无穷大，dp[0][src] = 0。表示 0 次航班后，在 src 的花费是 0。

  • 状态转移: 对于 i 从 1 到 k+1 (最多 k+1次航班)： 遍历所有的航班 [u, v, price]： dp[i][v] = min(dp[i][v], dp[i-1][u] + price)

    这个转移方程的含义是：乘坐 i 次航班到达 v 的最小花费，等于，乘坐 i-1 次航班到达 u 的最小花费，再加上从 u 到 v 的这一趟航班的花费。我们对所有能到达 v 的前驱 u 取一个最小值。

  • 最终结果: 答案就是 dp[1][dst], dp[2][dst], ..., dp[k+1][dst] 中的最小值。

这个思想其实和 Bellman-Ford 算法非常像。Bellman-Ford 就是通过 n-1 轮松弛操作来找到最短路径，每一轮松弛操作 i 都保证了找到的路径最多包含 i 条边。这里我们把轮数限制在 k+1 即可。

import java.util.Arrays;

class Solution4 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // dp[i][j] 表示经过 i 次航班到达城市 j 的最小花费
        // 这里可以优化空间，用两个一维数组滚动更新
        long[][] dp = new long[k + 2][n];
        for (long[] row : dp) {
            Arrays.fill(row, Long.MAX_VALUE);
        }

        // base case: 0次航班，在src，花费为0
        dp[0][src] = 0;

        for (int i = 1; i <= k + 1; i++) {
            // 先继承上一轮的结果，因为可以原地踏步
            System.arraycopy(dp[i - 1], 0, dp[i], 0, n);
            for (int[] flight : flights) {
                int u = flight[0];
                int v = flight[1];
                int price = flight[2];
                if (dp[i - 1][u] != Long.MAX_VALUE) {
                    dp[i][v] = Math.min(dp[i][v], dp[i - 1][u] + price);
                }
            }
        }

        long minCost = Long.MAX_VALUE;
        for (int i = 1; i <= k + 1; i++) {
            minCost = Math.min(minCost, dp[i][dst]);
        }

        return minCost == Long.MAX_VALUE ? -1 : (int) minCost;
    }
}

// 空间优化版本
class Solution4Optimized {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        long[] dp = new long[n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[src] = 0;

        for (int i = 0; i <= k; i++) {
            long[] next_dp = Arrays.copyOf(dp, n);
            for (int[] flight : flights) {
                int u = flight[0];
                int v = flight[1];
                int price = flight[2];
                if (dp[u] != Long.MAX_VALUE) {
                    next_dp[v] = Math.min(next_dp[v], dp[u] + price);
                }
            }
            dp = next_dp;
        }

        return dp[dst] == Long.MAX_VALUE ? -1 : (int) dp[dst];
    }
}

DP 解法代码非常简洁，思路清晰，把问题的层次感（航班次数）体现得淋漓尽致。

总结

回顾一下我们的解题思路：

  1. DFS 暴力搜：最直观，但会超时，是思考的起点。

  2. BFS 按层搜：比 DFS 聪明，一层层（按中转次数）扩展，避免了在单条路径上陷得太深。这是队列式分支限界法的体现。

  3. Dijkstra 贪心搜：在 BFS 的基础上，加入了优先队列，优先扩展成本最低的路径。这是优先队列式分支限界法，效率更高。但要注意改造状态，把中转次数也加进去。

  4. DP 迭代算：完全换了个思路，从状态定义的角度出发，精确计算出每一步（每一次航班）后到达各地的最低成本。代码清晰，逻辑严谨。

  • #5zu6k66