25年的第二题--旅行最短路径问题

暴力解法思路弗洛伊德算法全图最短路径搜集有 n 个点要每个点都走一遍枚举所有可能的访问顺序全排列 对每种顺序按顺序走算总距离 最后输出最小的总距离//计算任意两个点之间的最短路径暴力全部计算经过中转站后的最短路径//一种经典的求全图的最短路径算法privatestaticvoidfloyd(int[][]dist,intn){finalintINF1000000;//让每个点都走下这个中转站//并且我们都是把地点从1开始的所以这里一定注意循环for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){//只要中转站不是不可达的都试一下--这很暴力if(dist[i][k]!INF||dist[k][j]!INF){dist[i][j]Math.min(dist[i][j],dist[i][k]dist[k][j]);}}}}}功能函数2暴力枚举求解最小时间//寻找最短路径privatestaticintfindminway(int[][]dist,intn){//在搜索最短路劲的时候引入一个标记位boolean[]visnewboolean[n1];vis[1]true;// 固定从1号点出发// 2. 暴力 DFS 核心精简版只传必要参数 // now 当前在哪个点// cnt 已经走了几个点// cost 目前花了多少钱// vis 哪些点走过// dist 两点之间最短距离必须传// n 总共有几个点intmindfs(1,1,0,vis,dist,n);returnmin;}privatestaticintdfs(intnow,intcount,intcost,boolean[]vis,int[][]dist,intn){if(countn)returncost;// 递归出口所有点都走完了直接返回【这一条路的总花费】// 先设成无穷大表示还没找到路intminCost100000000;//循环N个点的探索for(inti1;in;i){if(!vis[i])//如果没有探索过{vis[i]true;//没有探索过的话继续往深处走。//完成了--计数功能花费时长统计功能,并且保留当前的节点的最小路径intcostnextdfs(i,count1,costdist[now][i],vis,dist,n);//保留最小的分支minCostMath.min(costnext,minCost);vis[i]false;}}returnminCost;}packagefushi.zhenti.shangji.lvxing;importjava.util.Arrays;importjava.util.Scanner;publicclassdaka{publicstaticvoidmain(String[]args){finalintINF1000000;ScannerscnewScanner(System.in);intmsc.nextInt();//定义边的数量intnsc.nextInt();//定义输入的地点数量int[][]distnewint[n1][n1];//定义n1个用来存储下对应下标的地点//初始化顶点之间的距离for(inti1;in;i){Arrays.fill(dist[i],INF);dist[i][i]0;//自己到自己为0}//读边的信息for(inti0;im;i){intusc.nextInt();//起点intvsc.nextInt();//终点intwsc.nextInt();//长度dist[u][v]w;dist[v][u]w;}floyd(dist,n);intminfindminway(dist,n);System.out.println(min);}//寻找最短路径privatestaticintfindminway(int[][]dist,intn){//在搜索最短路劲的时候引入一个标记位boolean[]visnewboolean[n1];vis[1]true;// 固定从1号点出发// 2. 暴力 DFS 核心精简版只传必要参数 // now 当前在哪个点// cnt 已经走了几个点// cost 目前花了多少钱// vis 哪些点走过// dist 两点之间最短距离必须传// n 总共有几个点intmindfs(1,1,0,vis,dist,n);returnmin;}privatestaticintdfs(intnow,intcount,intcost,boolean[]vis,int[][]dist,intn){if(countn)returncost;// 递归出口所有点都走完了直接返回【这一条路的总花费】// 先设成无穷大表示还没找到路intminCost100000000;//循环N个点的探索for(inti1;in;i){if(!vis[i])//如果没有探索过{vis[i]true;//没有探索过的话继续往深处走。//完成了--计数功能花费时长统计功能,并且保留当前的节点的最小路径intcostnextdfs(i,count1,costdist[now][i],vis,dist,n);//保留最小的分支minCostMath.min(costnext,minCost);vis[i]false;}}returnminCost;}//计算任意两个点之间的最短路径暴力全部计算经过中转站后的最短路径//一种经典的求全图的最短路径算法privatestaticvoidfloyd(int[][]dist,intn){finalintINF1000000;//让每个点都走下这个中转站//并且我们都是把地点从1开始的所以这里一定注意循环for(intk1;kn;k){for(inti1;in;i){for(intj1;jn;j){//只要中转站不是不可达的都试一下--这很暴力if(dist[i][k]!INFdist[k][j]!INF){dist[i][j]Math.min(dist[i][j],dist[i][k]dist[k][j]);}}}}}}1. 整体功能你的代码做了一件事从 1 号点出发遍历所有地点求最短路径总长度。两步核心Floyd求任意两点最短距离DFS 暴力枚举所有走法找最小值2. 初始化你写的for(inti1;in;i){Arrays.fill(dist[i],INF);dist[i][i]0;}数组开n1点编号从 1 开始每一行先全部填无穷大表示最开始都不可达自己到自己 03. 读入边你写的for(inti0;im;i){intusc.nextInt();intvsc.nextInt();intwsc.nextInt();dist[u][v]w;dist[v][u]w;}i 从 0 开始只是循环 m 次读 m 条路无向图双向距离一样4. Floyd 算法你写的for(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)k 中转站i 起点j 终点只有i 能到 k 且 k 能到 j才更新更新公式i→j 直接走 vs 经k中转取最短5. DFS 暴力搜索你写的dfs(now,count,cost,vis,dist,n)now当前在哪个点count已经走了几个点cost当前总花费vis标记哪些点走过走到count n→ 表示走完所有点返回花费枚举所有没走过的点 → 标记 → 递归 → 回溯最后返回最小花费6. 你的代码最关键的 3 个要点点从 1 开始所以循环都是i n二维数组必须一行一行 fillDFS 靠递归回溯枚举所有路线找最小值最终一句话总结你的代码先建图并初始化距离矩阵 → 用 Floyd 算出所有点之间的最短路径 → 用 DFS 暴力枚举所有遍历路线 → 返回最短总路径。