弗洛伊德算法
2023-02-26 12:27:27 时间
弗洛伊德(Floyd)算法图解分析
设置顶点vi到顶点vk的最短路径已知为Lik,顶点vk到vj的最短路径已知为Lkj,顶点vi到vj的路径为Lij,则vi到vj的最短路径为:min((Lik+Lkj),Lij),vk的取值为图中所有顶点,则可获得vi到vj的最短路径
至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj,是以同样的方式获得
弗洛伊德(Floyd)算法最佳应用-最短路径
胜利乡有7个村庄(A, B, C, D, E, F, G)
(福利推荐:阿里云、腾讯云、华为云服务器最新限时优惠活动,云服务器1核2G仅88元/年、2核4G仅698元/3年,点击这里立即抢购>>>)
各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里 问:如何计算出各村庄到 其它各村庄的最短距离?
代码示例
package com.wxit.floyd; import java.util.Arrays; /** * @Author wj **/ public class FloydAlgorithm { public static void main(String[] args) { //测试,图是否创建成功 char[] vertex = {'A','B','C','D','E','F','G'}; //创建邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0] = new int[]{ 0, 5, 7, N, N, N, 2}; matrix[1] = new int[]{ 5, 0, N, 9, N, N, 3}; matrix[2] = new int[]{ 7, N, 0, N, 8, N, N}; matrix[3] = new int[]{ N, 9, N, 0, N, 4, N}; matrix[4] = new int[]{ N, N, 8, N, 0, 5, 4}; matrix[5] = new int[]{ N, N, N, 4, 5, 0, 6}; matrix[6] = new int[]{ 2, 3, N, N, 4, 6, 0}; //创建Graph对象 Graph graph = new Graph(vertex.length,matrix,vertex); graph.show(); graph.floyd(); } } //创建图 class Graph { private char[] vertex; //存放顶点的数组 private int[][] dis; //保存,从各个顶点出发到其他顶点的距离,最后的结果,也是保留在该数组 private int[][] pre; //保存到达目标顶点的前驱节点 /** * 构造器 * @param length 大小 * @param matrix 邻接矩阵 * @param vertex 顶点数组 */ public Graph(int length,int[][] matrix,char[] vertex){ this.vertex = vertex; this.dis = matrix; this.pre = new int[length][length]; //对pre数组初始化,注意存放的是前驱节点的下标 for (int i = 0; i < length; i++) { Arrays.fill(pre[i],i); } } //显示pre数组和dis数组 public void show(){ //为了显示便于阅读,我们优化一下输出 char[] vertex = {'A','B','C','D','E','F','G'}; for(int k = 0; k <dis.length;k++){ //现将pre数组输出的一行 for (int i = 0; i < dis.length;i++){ System.out.print(vertex[pre[k][i]] + " "); } System.out.println(); //输出dis数组的一行数据 for (int i = 0;i < dis.length;i++){ System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + " "); } System.out.println(); System.out.println(); } } //弗洛伊德算法 public void floyd() { int len = 0;//变量保存距离 //对中间顶点进行遍历,k 就是中间顶点的下标[A,B,C,D,E,F,G] for (int k = 0; k < dis.length;k++){ //从i顶点开始出发[A,B,C,D,E,F,G] for (int i = 0; i < dis.length;i++){ //达到j顶点,[A,B,C,D,E,F,G] for (int j = 0; j < dis.length;j++){ len = dis[i][k] + dis[k][j];//求出从i顶点出发,经过k中间顶点,到达j顶点的距离 if (len < dis[i][j]){ //如果len小于dis[i][j] dis[i][j] = len;//更新距离 pre[i][j] = pre[k][j];//更新前驱节点 } } } } } }
你还在原价购买阿里云、腾讯云、华为云、天翼云产品?那就亏大啦!现在申请成为四大品牌云厂商VIP用户,可以3折优惠价购买云服务器等云产品,并且可享四大云服务商产品终身VIP优惠价,还等什么?赶紧点击下面对应链接免费申请VIP客户吧:
相关文章
- 基于ArgoCD的GitOps转型实战经验
- GitOps: Kubernetes CI/CD 的缺失环节
- Linux网络编程-TCP客户端如何获取要连接的服务端IP?
- 嵌入式Qt-表格使用测试
- PHP常见的几种数据结构
- php-fpm 是如何处理php 请求的
- [linux]执行pip安装的程序:command not found
- [linux]查看linux下端口占用
- [linux]scp指令
- [linux笔记]理清linux安装程序用到的(configure, make, make install)
- [git]git忽略文件
- linux根目录下文件夹概览
- php 生产kafka 不生效问题
- PHP二维数组取差集
- php 拉取 gz 文件进行解压后保存到自己的服务器
- go包管理代理网址无法访问
- go 连接redis
- mongo 笔记
- 2022-12-29:nsq是go语言写的消息队列。请问k3s部署nsq,yaml如何写?
- 不背锅运维:上篇:Go并发编程