自建外贸网站多少钱,邯郸房产网站,免费网站最新域名,cms 网站群文章目录 问题描述算法流程5分钟拿下 问题描述 一天小明捧着一本世界地图在看#xff0c;突然小明拿起笔#xff0c;将他最爱的那些城市标记出来#xff0c;并且随机的将这些城市中的某些用线段两两连接起来。 小明量出了每条线段的长度#xff0c;现在小明想知道在这些线段… 文章目录 问题描述算法流程5分钟拿下 问题描述 一天小明捧着一本世界地图在看突然小明拿起笔将他最爱的那些城市标记出来并且随机的将这些城市中的某些用线段两两连接起来。 小明量出了每条线段的长度现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。 输入包含多组测试数据。 每组输入第一行为两个正整数nn10和mmn*(n-1)/2n表示城市个数m表示线段个数。 接下来m行每行输入三个整数ab和l表示a市与b市之间存在一条线段线段长度为l。a与b不同 每组最后一行输入两个整数x和y表示问题x市与y市之间的最短距离是多少。x与y不同 城市标号为1~nl20。 算法流程
需要维护一个distdist[a][b] l表示从a点到b点需要的距离权重。 如果没有给出两点之间的权重我们认为这两个点之间无限远为了防止相加超出整数范围INF Integer.MAX_VALUE / 2 。
import java.util.*;
class Main{public static final int INF Integer.MAX_VALUE / 2;public static void main (String[] args) {Scanner scanner new Scanner(System.in);while(scanner.hasNext()){// n个城市int n scanner.nextInt();// m条线段int m scanner.nextInt();//dist[a][b]lab两个顶点的举例是l。int [][] dist new int [n 1][n 1];// 初始化dist矩阵 自己到自己的距离是0默认是INF最大值。for(int i 1 ;i n ; i ){for(int j 1 ; j n ; j ){if(i j){dist[i][j] 0;}else{dist[i][j] INF;}}}// 放入我们的数据while(m -- 0){int a scanner.nextInt();int b scanner.nextInt();int l scanner.nextInt();// 放入distfor(int i 1 ; i n ; i ){for(int j 1 ;j n ; j ){//无向图a到bb到a距离一样dist[a][b] l;dist[b][a] l;}}}// 算法核心部分 计算图中所有顶点对的最小距离// 遍历每个顶点将i作为其他所有顶点对的中转点。for(int i 1 ; i n ; i){// 遍历所有路径可能的起始点for(int j 1 ; j n ; j ){// 遍历所有路径可能的终点for(int k 1 ; k n ; k ){// 如果起点到中转点的距离 中转点到终点的距离 起始点到终点的距离if(dist[j][i] dist[i][k] dist[j][k]){// 起始点到终点的距离 起点到中转点的距离 中转点到终点的距离dist[j][k] dist[j][i] dist[i][k];}}}}// 读取要查询的两个城市int x scanner.nextInt();int y scanner.nextInt();System.out.println(dist[x][y] INF ? No path : dist[x][y]);}}
}5分钟拿下
该算法用来找出图中所有顶点对之间的最小距离。注意所有顶点对之间的最小距离最后都放在dist里了。
这里说成距离不好理解其实算的是一种权重。
我们举一个简单的例子从家到学校我们看成两个节点之前你一直是坐豪华轿车需要花10块钱看成两点之间的距离权重。 后来你家破产了10块钱都没有了于是你要寻找一种最便宜最经济的方法。你有很多认识的同学i1i2i3不同节点。 你在想我先坐公交去他们家然后再坐公交去学校这样可能便宜很多。于是你找了所有的同学一个一个尝试先从你家到同学家再从同学家到学校。 过程中你自己维护了一个dist每次有新的省钱路径你都记录到dist中这样最后从你家到学校的那个dist就是最便宜的最短距离/权重。
当然这只是其中一个简化的模型我们分析一下下面的代码 第一层for循环就是找所有人的家节点把每个人的家作为中间点。 第二层for循环就是找所有的起点这里我们维护的dist是图中所有节点之间的最小权重。因为只有把图中的所有节点都跑一遍你才能发现最省钱的路径。 第三层for循环找所有的终点。 如果起点到中转点的距离 中转点到终点的距离 起始点到终点的距离就更新起始点到终点的距离。
在算法中你不仅检查了朋友的家而且检查了所有人的家不愧是你。这就确保了你找到了最短的路径因为你没有忽略任何可能的路线。这就是Floyd-Warshall算法之所以能够得出正确答案的原因。 // 遍历每个顶点将i作为其他所有顶点对的中转点。for(int i 1 ; i n ; i){// 遍历所有路径可能的起始点for(int j 1 ; j n ; j ){// 遍历所有路径可能的终点for(int k 1 ; k n ; k ){// 如果起点到中转点的距离 中转点到终点的距离 起始点到终点的距离if(dist[j][i] dist[i][k] dist[j][k]){// 起始点到终点的距离 起点到中转点的距离 中转点到终点的距离dist[j][k] dist[j][i] dist[i][k];}}}}如果觉得写的不错可以点一个关注~
