java实现Floyd算法
发布时间:2020-12-14 20:10:36 所属栏目:Java 来源:网络整理
导读:Floyd算法:用于多源最短路径的求解,算出来的是所有的节点到其余各节点之间的最短距离。 该算法的思路是:首先初始化距离矩阵,然后从第一个点开始逐渐更新矩阵点值。d[i][j]表示从i点到j点的距离。第k次更新时,判断d[i][k]+d[k][j]与d[i][j]的大小,如果前
Floyd算法:用于多源最短路径的求解,算出来的是所有的节点到其余各节点之间的最短距离。 该算法的思路是:首先初始化距离矩阵,然后从第一个点开始逐渐更新矩阵点值。d[i][j]表示从i点到j点的距离。第k次更新时,判断d[i][k]+d[k][j]与d[i][j]的大小,如果前者小,则更新这个值,否则不变。 给一个例子: 具体的floyd实现算法如下[java] view plain copy package com.blyang; public class Floyd { int[][] Matrix; char[] Nodes; private final int INF = Integer.MAX_VALUE; public Floyd(char[] Nodes,int[][] Matrix){ this.Nodes = Nodes; this.Matrix = Matrix; } public void floyd(){ int[][] distance = new int[Nodes.length][Nodes.length]; // 初始化距离矩阵 for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ distance[i][j] = Matrix[i][j]; } } //循环更新矩阵的值 for(int k=0; k<Nodes.length; k++){ for(int i=0; i<Nodes.length; i++){ for(int j=0; j<Nodes.length; j++){ int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j]; if(distance[i][j] > temp){ distance[i][j] = temp; } } } } // 打印floyd最短路径的结果 System.out.printf("floyd: n"); for (int i = 0; i < Nodes.length; i++) { for (int j = 0; j < Nodes.length; j++) System.out.printf("%12d ",distance[i][j]); System.out.printf("n"); } } } 在实现之后,针对上图的点和权值,给定一个测试: package com.blyang; public class Main { public static void main(String[] args) { int INF = Integer.MAX_VALUE; char[] Nodes = {'0','1','2','3'}; int matrix[][] = { /*A*//*B*//*C*//*D*/ /*A*/ { 0,1,2,1},/*B*/ { INF,INF,INF},/*C*/ { INF,3,/*D*/ { INF,0},}; int[] dist = new int[Nodes.length]; Floyd floyd = new Floyd(Nodes,matrix); floyd.floyd(); } } 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |