java实现Floyd算法

时间:2021-07-10 08:05:07

Floyd算法:用于多源最短路径的求解,算出来的是所有的节点到其余各节点之间的最短距离。

该算法的思路是:首先初始化距离矩阵,然后从第一个点开始逐渐更新矩阵点值。d[i][j]表示从i点到j点的距离。第k次更新时,判断d[i][k]+d[k][j]与d[i][j]的大小,如果前者小,则更新这个值,否则不变。

给一个例子:

java实现Floyd算法

具体的floyd实现算法如下[java] view plain copy

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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");
    }
  }
}

在实现之后,针对上图的点和权值,给定一个测试:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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,  110},
     };
       
    int[] dist = new int[Nodes.length];
   
    Floyd floyd = new Floyd(Nodes, matrix);
    floyd.floyd();
 
  }
   
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:http://blog.csdn.net/sinat_22013331/article/details/51000331