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[][] 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();      }      }

感谢各位的阅读！关于“java实现Floyd算法的示例”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！