🌼5.模板代码以及例题训练
代码转换：模板为bellman_ford函数，函数的每个操作我都搭配上了讲解。
import java.util.*; public class Main { static int N=510; static int M=10010; static List<Node> list=new ArrayList<>(); static int[] dist=new int[N]; static int[] backup=new int[N]; static int n,m,k; static boolean flag=false; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); k=sc.nextInt(); for (int i = 0; i <m; i++) { int a=sc.nextInt(); int b=sc.nextInt(); int w=sc.nextInt(); list.add(new Node(a,b,w)); } int t=bellman_ford(); if(t==-1&&flag) System.out.println("impossible"); else System.out.println(t); } static int bellman_ford(){ //和Dijkstra一样的初始化步骤 Arrays.fill(dist,0x3f3f3f3f); dist[1]=0; //限制k条边，所以只循环K次 for (int i = 0; i < k; i++) { //每次松弛操作前先备份一下 backup=Arrays.copyOfRange(dist,0,N); //开始松弛操作 for (int j = 0; j < m; j++) { int a=list.get(j).a; int b=list.get(j).b; int w=list.get(j).w; //和Dijkstra的差不多，只不过一定要使用backup进行松弛 dist[b]=Math.min(dist[b],backup[a]+w); } } //注意这里是除以2，因为有负数的情况，在无解的情况下不一定刚好等于0x3f3f3f3f if (dist[n]>0x3f3f3f3f/2){ flag=true; return -1; }else return dist[n]; } } class Node{ int a,b,w; public Node(int a, int b, int w) { this.a = a; this.b = b; this.w = w; } }
🍄K站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
来源：力扣（LeetCode）
题目链接：K 站中转内最便宜的航班https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
这是一道bellman-ford的模板题，从题目的名字就已经告诉我们要使用该算法了。K站中转——限制边数，最便宜航班——最短路问题。在这里我们要注意一个问题，K次中转是K条边吗？当然不是，转了一次车说明做了两种不同的车，所以K次中转我们应该是K+1条边。
在这里我们直接使用上面的模板即可：
class Solution { //有边数限制使用贝尔曼夫算法 int N=100; int M=5010; List<Node> list=new ArrayList<>(); int[] dist=new int[N]; int[] backup=new int[N]; int n,m,k,src,dst; public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { this.n=n; this.m=flights.length; //k次中转是k条边 this.k=k+1; this.src=src; this.dst=dst; for(int[] s:flights){ int a=s[0]; int b=s[1]; int w=s[2]; list.add(new Node(a,b,w)); } int t=bellman_ford(); return t; } int bellman_ford(){ Arrays.fill(dist,0x3f3f3f3f); dist[src]=0; for(int i=0;i<k;++i){ backup=Arrays.copyOfRange(dist,0,N); for(int j=0;j<m;++j){ int a=list.get(j).a; int b=list.get(j).b; int w=list.get(j).w; dist[b]=Math.min(dist[b],backup[a]+w); } } if(dist[dst]>0x3f3f3f3f/2) return -1; else return dist[dst]; } } class Node{ int a,b,w; public Node(int a, int b, int w) { this.a = a; this.b = b; this.w = w; } }
🚀6.课后总结
bellman-ford算法是一个比较简单暴力的算法，可能有些地方我讲的不太清楚，大家可能评论区或者私信询问都可以，当然对于最短路算法大家实在理解不了的可以先背下来模板直接使用，用着用着就能慢慢明白了（我就是这样哈哈哈哈）。 bellman-ford的模板还是比较简单粗暴的，两次循环即可。
