java实现Floyd算法

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,  0, INF, INF},
     /*C*/ { INF,  3,  0,  1},
     /*D*/ { INF,  1,  1,  0},
     }; 

    int[] dist = new int[Nodes.length]; 

    Floyd floyd = new Floyd(Nodes, matrix);
    floyd.floyd(); 

  } 

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • java算法导论之FloydWarshall算法实现代码

    摘要: 算法导论之FloydWarshall算法 求一个图中任意两点之间的最短路径 FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 如果普通求最短路径,可以对图进行V次(顶点数)BellmanFord算法. 这样的话时间复杂度为EV^2 如果是稀疏图,则近似于V^3 但是如果是密集图,则时间复杂度会近似达到V^4,这种情况需要优化,这里FloydWarshall通过动态规划进行优化 ,并且使用邻接矩阵来表示图. 实例代码: package org.loda.graph;

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • Java实现Floyd算法的示例代码

    Java实现Floyd算法的示例代码

    目录 一 问题描述 二 代码 三 实现 一 问题描述 求节点0到节点2的最短路径. 二 代码 package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int dist[][] = new int[MaxVnum][MaxVnum

  • java实现Floyd算法

    java实现Floyd算法

    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[][] Ma

  • Java Floyd算法求有权图（非负权）的最短路径并打印

    状态转移方程:d(i,j) = min(d(i,j),d(i,k)+d(k,j)),其中i<k<j 思路对于每一个k(i<k<j),全部遍历下来之后,肯定会发生一次有效的比较 public class FloydTest { private static int[][] matrix; private static int[][] path; public static void main(String[] args) { initMatrixAndPath( new int[][

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • java实现Fibonacci算法实例

    本文实例讲述了java实现Fibonacci算法的方法.分享给大家供大家参考.具体如下: package com.yenange.test2; import java.util.Scanner; public class Fibonacci { private static Scanner input = new Scanner(System.in); public static void main(String[] args) { System.out.println("-----------

  • Java TreeMap排序算法实例

    本文实例讲述了Java TreeMap排序算法.分享给大家供大家参考,具体如下: TreeMap 和 HashMap 用法大致相同,但实际需求中,我们需要把一些数据进行排序: 以前在项目中,从数据库查询出来的数据放在List中,顺序都还是对的,但放在HashMap中,顺序就完全乱了. 为了处理排序的问题: 1. 对于一些简单的排序,如:数字,英文字母等 TreeMap hm = new TreeMap<String, String>(new Comparator() { public int

  • Java抽奖抢购算法

    本文示例为大家分享了Java抽奖抢购算法,供大家参考,具体内容如下 应用场景 单件奖品抢购(可限时) 多件奖品按概率中奖(可限时.可不限量) 代码实现 表结构: --抽奖设置 create table AWARD_INFO ( ID NUMBER(11) not null, ACT_ID NUMBER(11), --活动ID NUM NUMBER(11), --奖品总量(0为不限量) REST NUMBER(11), --奖品余量 ODDS NUMBER(11) default 0, --中奖概

随机推荐