时代Java，与您同行！关注微信公众号，关注前沿技术，微信搜索：nowjava或时代Java，也可点击这里扫码关注

时代Java

Java 所有节点对之间的最短路径

欢马劈雪

工程师 (已认证)

原创分享签约作者

发表于实例源码

624

所有节点对之间的最短路径

实例源码：

源代码：

执行

执行中...

import java.util.Arrays;

//Runtime: O(V^3). Shortest path between all the pairs of nodes, works with negative cycle.

public class FloydWarshall {
/** 
 来自 nowjava.com - 时  代  Java**/

//gWeights[i][j] must contain the weight of the edge ij if there is an edge i->j, 0 if i=j, otherwise +infinity if there is no edge i->j

/**

* @param gWeights it's a matrix V*V where V is the number of verticies. gWeights[u][v] = w if there is an edge between u and v of weight w, gWeights[u][u]=0, gWeights[u][v]=DOUBLE.POSITIVE_INFINITY if there is no edge between u and v

* @return matrix[V][V] where matrix[u][v]=min distance to go from u to v

public static double[][] floydWarshall(double[][] gWeights) {

double[][] minDistances = gWeights.clone();

int[][] paths = new int[gWeights.length][gWeights[0].length]; //paths[i][j] contains the optimal predecessor of j to reach i

//initialize the current predessors with the edges of the graph

for (int i = 0; i < gWeights.length; i++) {

for (int j = 0; j < gWeights[0].length; j++) {

if (gWeights[i][j] < Double.POSITIVE_INFINITY && i != j) { //means there is an edge between i and j

paths[i][j] = i; //mark i as the predecessor of j to reach i

} else {

paths[i][j] = -1; //there is not edge, so mark -1

}

}/**来 自 nowjava - 时  代  Java**/

}

//for every pair test if there is a shorter path gowing through another node

for (int k = 0; k < gWeights.length; k++) {// test if ik->kj shorter than current i->j

for (int i = 0; i < gWeights.length; i++) {

for (int j = 0; j < gWeights.length; j++) { //pair i,j

if (minDistances[i][j] > minDistances[i][k]

+ minDistances[k][j]) {

minDistances[i][j] = minDistances[i][k]

+ minDistances[k][j];

paths[i][j] = paths[k][j]; //the predecessor of j to reach i is the predecessor of j to reach k

}

//if one distance from a node to itself changed to a negative value, it means that there is a negative cycle in the graph, => return null

for (int i = 0; i < minDistances.length; i++) {

if (minDistances[i][i] != 0) {

return null; //there is a negative cycle in the graph

}

return minDistances;

}

public static void main(String[] args) {

double[][] gWeights = new double[][] {

{ 0, 3, 6, 15 },

{ Double.POSITIVE_INFINITY, 0, -2, Double.POSITIVE_INFINITY },

{ Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, 2 },

{ 1, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0 } };

System.out.println("The weights matrix representing the graph :");
/**代码未完, 请加载全部代码(NowJava.com).**/

编辑/阅读全部代码

执行结果：

本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。

编辑于 2020-03-26 09:23:272020-03-26 09:23:27

实例源码

实例源码订阅