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

for(int j=0; j

distance[i][j] = Matrix[i][j];

}

}

//循环更新矩阵的值

for(int k=0; k

for(int i=0; i

for(int j=0; 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();

}

}

for(int j=0; j

distance[i][j] = Matrix[i][j];

}

}

//循环更新矩阵的值

for(int k=0; k

for(int i=0; i

for(int j=0; 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();

}

}

distance[i][j] = Matrix[i][j];

}

}

//循环更新矩阵的值

for(int k=0; k

for(int i=0; i

for(int j=0; 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();

}

}

for(int i=0; i

for(int j=0; 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();

}

}

for(int j=0; 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();

}

}

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();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。