news 2026/8/28 21:48:14

算法题 K 站中转内最便宜的航班

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
算法题 K 站中转内最便宜的航班

K 站中转内最便宜的航班

问题描述

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

给你三个整数src(出发城市)、dst(目的地城市)和k(最多中转次数),返回从srcdst最多经过 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 无法处理边数限制。

核心

  1. 中转次数:最多 k 次中转意味着最多使用 k+1 条边
  2. 动态规划:可以按边数(或中转次数)进行状态转移

方法

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

Bellman-Ford 核心思想

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

代码实现

方法一: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}

关键点

  1. 中转次数

    • k次中转 = k+1条边
    • Bellman-Ford需要执行k+1轮
  2. 临时数组

    • 使用临时数组避免在同一轮中多次更新
    • Bellman-Ford算法的核心
  3. 边界情况处理

    • 起点等于终点:费用为0
    • 无法到达:返回-1
    • 直接可达:1条边,0次中转

常见问题

  1. 为什么不能用Dijkstra算法?

    • Dijkstra假设一旦找到最短路径就不会被更新
    • 这里路径可能更长但中转次数更少,需要考虑所有可能性
  2. 临时数组?

    • 确保每轮操作只基于上一轮的结果
    • 避免在同一轮中使用刚更新的值,导致错误的多步更新
  3. 如何处理负权边?

    • Bellman-Ford天然支持负权边
版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/8/28 11:14:28

DeepSeek在线使用:AI编程助手的革命性体验

快速体验 打开 InsCode(快马)平台 https://www.inscode.net输入框内输入如下内容&#xff1a; 使用DeepSeek在线平台&#xff0c;创建一个能够自动生成Python代码的AI助手。要求&#xff1a;1. 根据用户输入的自然语言描述生成相应的Python代码&#xff1b;2. 支持代码错误检测…

作者头像 李华
网站建设 2026/8/27 22:17:47

【UE5.3】vrm角色建立Control Rig

步骤在内容浏览器中找到“CR_VRoidSimpleUE5Body”复制一份到项目路径下并重命名打开这个Control Rig&#xff0c;修改预览网格体找到“WBP_ControlRig”点击“运行编辑器工具控件”在打开的界面中先选择“Dst Control Rig BP”&#xff0c;然后点击【Generate AllRig/BodyRig】…

作者头像 李华
网站建设 2026/8/27 12:54:39

咸鸭蛋作坊升级:工业化批量腌制技术指南

快速体验 打开 InsCode(快马)平台 https://www.inscode.net输入框内输入如下内容&#xff1a; 创建咸鸭蛋生产管理系统原型&#xff1a;1) 产能计算器&#xff08;根据缸体尺寸推算单批产量&#xff09;2) 标准化作业流程图&#xff08;分级→清洗→装筐→腌制→质检&#xff…

作者头像 李华
网站建设 2026/8/28 8:08:47

31、内存管理的深入剖析

内存管理的深入剖析 1. 字节比较 在内存操作中,字节比较是一项基础且重要的任务。类似于 strcmp() 函数, memcmp() 用于比较两块内存是否相等: #include <string.h> int memcmp (const void *s1, const void *s2, size_t n);调用此函数会比较 s1 和 s2 的…

作者头像 李华
网站建设 2026/8/27 3:16:11

33、基础信号管理:原理、操作与应用

基础信号管理:原理、操作与应用 1. 信号基本行为设置 在信号处理中,有两个重要的常量用于设置信号的行为: - SIG_DFL :将 signo 指定的信号行为设置为默认行为。例如,对于 SIGPIPE 信号,进程会终止。 - SIG_IGN :忽略 signo 指定的信号。 signal() 函数用…

作者头像 李华
网站建设 2026/8/26 6:42:44

开源数据智能体推荐

针对想进行二次开发&#xff08;Secondary Development&#xff09;的需求&#xff0c;选择开源项目时需要重点考察代码的模块化程度、RAG&#xff08;检索增强生成&#xff09;与SQL生成的结合机制、以及对私有化部署的支持。 以下是目前GitHub上最活跃、质量最高&#xff0c;…

作者头像 李华