算法题 K 站中转内最便宜的航班-程序员充电站

K 站中转内最便宜的航班

问题描述

有n个城市，编号从0到n - 1。给你一个航班数组flights，其中flights[i] = [from_i, to_i, price_i]表示从城市from_i到城市to_i的航班价格为price_i。

给你三个整数src（出发城市）、dst（目的地城市）和k（最多中转次数），返回从src到dst且最多经过 k 次中转的最便宜价格。如果没有这样的路线，返回-1。

注意：中转次数 = 航班次数 - 1。例如，直接飞行（0次中转）使用1个航班。

示例：

输入: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 输出: 700 解释: 在最多 1 次中转的情况下，最便宜的路线是 0->1->3，总费用为 100 + 600 = 700。

算法思路

带限制条件的最短路径问题，不能直接使用 Dijkstra 算法，Dijkstra 无法处理边数限制。

核心：

中转次数：最多 k 次中转意味着最多使用 k+1 条边
动态规划：可以按边数（或中转次数）进行状态转移

方法：

Bellman-Ford 算法：天然支持边数限制
动态规划：dp[stops][city]表示经过 stops 次中转到达 city 的最小费用
BFS + 剪枝：按层数遍历，效率低

Bellman-Ford 核心思想：

初始化：起点费用为0，其他为无穷大
迭代 k+1 次（最多 k+1 条边）
每次迭代中，基于上一轮的结果更新当前轮的最短距离
使用临时数组避免在同一轮中多次更新

代码实现

方法一：Bellman-Ford 算法

importjava.util.*;classSolution{/** * 使用Bellman-Ford算法解K站中转内最便宜的航班 * * @param n 城市数量 * @param flights 航班信息数组，每个元素为[出发城市, 到达城市, 价格] * @param src 出发城市 * @param dst 目的地城市 * @param k 最多中转次数 * @return 最便宜价格，如果不可达返回-1 */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// 初始化距离数组，dist[i]表示到达城市i的最小费用int[]dist=newint[n];Arrays.fill(dist,Integer.MAX_VALUE);dist[src]=0;// Bellman-Ford算法：最多进行k+1轮松弛操作// 最多k次中转，所以最多k+1条边for(intstops=0;stops<=k;stops++){// 创建临时数组，避免在同一轮中使用更新后的值int[]tempDist=Arrays.copyOf(dist,n);booleanupdated=false;// 遍历所有航班for(int[]flight:flights){intfrom=flight[0];intto=flight[1];intprice=flight[2];// 如果from城市在上一轮中可达，尝试更新to城市的费用if(dist[from]!=Integer.MAX_VALUE){intnewCost=dist[from]+price;if(newCost<tempDist[to]){tempDist[to]=newCost;updated=true;}}}// 如果本轮没有更新，提前结束if(!updated){break;}// 更新距离数组dist=tempDist;}// 返回结果returndist[dst]==Integer.MAX_VALUE?-1:dist[dst];}}

方法二：动态规划

classSolution{/** * 使用动态规划解K站中转内最便宜的航班 * * @param n 城市数量 * @param flights 航班信息 * @param src 出发城市 * @param dst 目的地城市 * @param k 最多中转次数 * @return 最便宜价格 */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// dp[i][j] 表示经过最多i次中转到达城市j的最小费用// i的范围是0到k+1（0次中转到k+1次中转）int[][]dp=newint[k+2][n];// 初始化：所有费用设为无穷大for(inti=0;i<=k+1;i++){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 起点费用为0（0次中转到达起点）for(inti=0;i<=k+1;i++){dp[i][src]=0;}// 动态规划填表for(intstops=1;stops<=k+1;stops++){// 继承上一轮的结果（不使用新的航班）for(intcity=0;city<n;city++){dp[stops][city]=dp[stops-1][city];}// 尝试使用所有航班进行更新for(int[]flight:flights){intfrom=flight[0];intto=flight[1];intprice=flight[2];// 如果from城市在stops-1次中转内可达if(dp[stops-1][from]!=Integer.MAX_VALUE){intnewCost=dp[stops-1][from]+price;dp[stops][to]=Math.min(dp[stops][to],newCost);}}}// 返回最多k次中转（即k+1条边）的结果returndp[k+1][dst]==Integer.MAX_VALUE?-1:dp[k+1][dst];}}

方法三：Dijkstra 变种（带状态）

importjava.util.*;classSolution{/** * 使用Dijkstra算法的变种，状态包含(城市, 中转次数) */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// 构建邻接表List<int[]>[]graph=newList[n];for(inti=0;i<n;i++){graph[i]=newArrayList<>();}for(int[]flight:flights){graph[flight[0]].add(newint[]{flight[1],flight[2]});}// 优先队列：[费用, 城市, 中转次数]PriorityQueue<int[]>pq=newPriorityQueue<>((a,b)->a[0]-b[0]);pq.offer(newint[]{0,src,0});// 记录到达每个城市在不同中转次数下的最小费用int[][]minCost=newint[n][k+2];for(inti=0;i<n;i++){Arrays.fill(minCost[i],Integer.MAX_VALUE);}minCost[src][0]=0;while(!pq.isEmpty()){int[]current=pq.poll();intcost=current[0];intcity=current[1];intstops=current[2];// 如果到达目的地，返回费用if(city==dst){returncost;}// 如果中转次数已达到上限，不能继续if(stops>k){continue;}// 遍历邻居for(int[]neighbor:graph[city]){intnextCity=neighbor[0];intprice=neighbor[1];intnewCost=cost+price;intnewStops=stops+1;// 如果找到更优的路径if(newCost<minCost[nextCity][newStops]){minCost[nextCity][newStops]=newCost;pq.offer(newint[]{newCost,nextCity,newStops});}}}return-1;}}

算法分析

时间复杂度：
- Bellman-Ford：O(k × E)，其中E是航班数量
- 动态规划：O(k × E)
- Dijkstra变种：O(E × k × log(V × k))
空间复杂度：
- Bellman-Ford：O(V)
- 动态规划：O(V)
- Dijkstra变种：O(V × k)

算法过程

n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Bellman-Ford：

初始化：

dist = [0, ∞, ∞, ∞]

第1轮（0次中转，1条边）：

处理航班[0,1,100]：dist[1] = min(∞, 0+100) = 100
其他航班的from城市不可达
dist = [0, 100, ∞, ∞]

第2轮（1次中转，2条边）：

基于第1轮的dist = [0, 100, ∞, ∞]
处理航班[1,3,600]：dist[3] = 100 + 600 = 700
处理航班[1,2,100]：dist[2] = 100 + 100 = 200
航班[2,3,200]不能使用，因为第1轮中dist[2] = ∞
所以dist[3] = 700

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]flights1={{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};System.out.println("Test 1: "+solution.findCheapestPrice(4,flights1,0,3,1));// 700// 测试用例2：无法到达int[][]flights2={{0,1,100},{1,2,100}};System.out.println("Test 2: "+solution.findCheapestPrice(3,flights2,0,2,0));// -1 (需要1次中转，但k=0)// 测试用例3：直接可达int[][]flights3={{0,1,100}};System.out.println("Test 3: "+solution.findCheapestPrice(2,flights3,0,1,0));// 100// 测试用例4：多条路径int[][]flights4={{0,1,100},{0,2,500},{1,2,100}};System.out.println("Test 4: "+solution.findCheapestPrice(3,flights4,0,2,1));// 200// 测试用例5：中转次数为0int[][]flights5={{0,1,100},{1,2,100},{0,2,500}};System.out.println("Test 5: "+solution.findCheapestPrice(3,flights5,0,2,0));// 500// 测试用例6：大价格值int[][]flights6={{0,1,1000000},{1,2,1000000}};System.out.println("Test 6: "+solution.findCheapestPrice(3,flights6,0,2,1));// 2000000// 测试用例7：起点等于终点int[][]flights7={{0,1,100}};System.out.println("Test 7: "+solution.findCheapestPrice(2,flights7,0,0,0));// 0// 测试用例8：复杂的多路径int[][]flights8={{0,1,1},{0,2,5},{1,2,1},{2,3,1}};System.out.println("Test 8: "+solution.findCheapestPrice(4,flights8,0,3,1));// -1 (需要2次中转)System.out.println("Test 9: "+solution.findCheapestPrice(4,flights8,0,3,2));// 3 (0->1->2->3)// 测试用例10：环路情况int[][]flights10={{0,1,100},{1,2,100},{2,0,100},{1,3,600}};System.out.println("Test 10: "+solution.findCheapestPrice(4,flights10,0,3,1));// 700}