Floyd(弗洛伊德)算法求解每对顶点之间的距离(Java语言)

简介: Floyd(弗洛伊德)算法求解每对顶点之间的距离(Java语言)

1、Floyd(弗洛伊德)算法

Floyd(弗洛伊德)算法求解每对顶点之间的距离(Java语言)

2、设计思想:

利用两个数组

Floy【i】【j】存储 i—>j 的路径长度

Path【i】【j】存储的是 i—>j 的中间节点

利用三重循环

第一层是取不同的中间节点

第二层是取图中不同起点

第三层是取不同终点

如果floy[i][j]>floy[i][k]+floy[k][j],则表明通过该中间节点的路径小于直接到达,经过这三次循环不断修正各个节点之间的路径,最终得到的Floy数组即为最优路径

代码:

/**
 *作者:魏宝航
 *2020年11月27日,上午10:27
 */
import org.omg.CORBA.INTERNAL;
import com.sun.jndi.url.iiopname.iiopnameURLContextFactory;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class MatrixUDG {
    private char[] mVexs;
    private int[][] mMatrix;
    private int num;
    public MatrixUDG(char[] vexs, char[][] edges) {
        num = vexs.length;
        mVexs = new char[num];
        for (int i = 0; i < mVexs.length; i++)
            mVexs[i] = vexs[i];
        mMatrix = new int[num][num];
        for(int i=0;i<num;i++){
            for(int j=0;j<num;j++){
                if(edges[i][j]=='∞'){
                    mMatrix[i][j]=Integer.MAX_VALUE;
                }else{
                    mMatrix[i][j]=Integer.parseInt(edges[i][j]+"");
                }
            }
        }
    }
    public void print() {
        System.out.printf("Martix Graph:\n");
        for (int i = 0; i < mVexs.length; i++) {
            for (int j = 0; j < mVexs.length; j++){
                if(mMatrix[i][j]<Integer.MAX_VALUE){
                    System.out.printf("%d ", mMatrix[i][j]);
                }else{
                    System.out.print("∞ ");
                }
            }
            System.out.printf("\n");
        }
    }
   public void Floyd(int x,int y) {
     int[][] floy=new int[1000][1000]; //存储i-j的距离
     int[][] path=new int[1000][1000];//存储i-j的中间节点
     for(int i=0;i<num;i++) {
       for(int j=0;j<num;j++) {
         floy[i][j]=this.mMatrix[i][j];
         if(i!=j&&this.mMatrix[i][j]<Integer.MAX_VALUE) {
           path[i][j]=i;
         }
         else {
           path[i][j]=-1;
         }
       }
     }
     for(int k=0;k<num;k++) {//中间节点
       for(int i=0;i<num;i++) {//起点
         for(int j=0;j<num;j++) {//终点
           if(floy[i][j]>floy[i][k]+floy[k][j]&&(floy[i][k]+floy[k][j])>=0) {
             floy[i][j]=floy[i][k]+floy[k][j];
             path[i][j]=path[k][j];
           }
         }
       }
     }
     System.out.println("每对顶点的最短路径如下:");
     for(int i=0;i<num;i++) {
       for(int j=0;j<num;j++) {
         System.out.print(floy[i][j]+" ");
       }
       System.out.println();
     }
     System.out.println(x+"与"+y+"之间的最短路径为"+floy[x][y]);
   }
    public static void main(String[] args) {
        char[] vexs={'0','1','2','3'};
        char[][] edges=new char[][]{
                {'0','5','∞','7'},
                {'∞','0','4','2'},
                {'3','3','0','2'},
                {'∞','∞','1','0'},
        };
        MatrixUDG g=new MatrixUDG(vexs,edges);
        g.print();
        g.Floyd(0, 3);
    }
}


目录
相关文章
|
7天前
|
存储 缓存 Java
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
32 3
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
|
13天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
1月前
|
Oracle Java 关系型数据库
Java基础(一):语言概述
Java基础(一):语言概述
52 15
Java基础(一):语言概述
|
4天前
|
存储 监控 算法
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
|
7天前
|
缓存 Java 应用服务中间件
java语言后台管理若依框架-登录提示404-接口异常-系统接口404异常如何处理-登录验证码不显示prod-api/captchaImage 404 (Not Found) 如何处理-解决方案优雅草卓伊凡
java语言后台管理若依框架-登录提示404-接口异常-系统接口404异常如何处理-登录验证码不显示prod-api/captchaImage 404 (Not Found) 如何处理-解决方案优雅草卓伊凡
35 5
|
26天前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
27天前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
68 16
|
26天前
|
存储 监控 算法
内网监控系统之 Go 语言布隆过滤器算法深度剖析
在数字化时代,内网监控系统对企业和组织的信息安全至关重要。布隆过滤器(Bloom Filter)作为一种高效的数据结构,能够快速判断元素是否存在于集合中,适用于内网监控中的恶意IP和违规域名筛选。本文介绍其原理、优势及Go语言实现,提升系统性能与响应速度,保障信息安全。
29 5
|
1月前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
30天前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
62 6