Java 所有节点对之间的最短路径
所有节点对之间的最短路径
实例源码：
源代码：
执行
执行中...
x
1
2
import java.util.Arrays;3
4
5
//Runtime: O(V^3). Shortest path between all the pairs of nodes, works with negative cycle.6
7
public class FloydWarshall {8
/** 9
来自 nowjava.com - 时 代 Java**/10
11
//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->j12
13
/**14
15
* 16
17
* @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 v18
19
* @return matrix[V][V] where matrix[u][v]=min distance to go from u to v20
21
*/22
23
public static double[][] floydWarshall(double[][] gWeights) {24
25
double[][] minDistances = gWeights.clone();26
27
int[][] paths = new int[gWeights.length][gWeights[0].length]; //paths[i][j] contains the optimal predecessor of j to reach i28
29
//initialize the current predessors with the edges of the graph30
31
for (int i = 0; i < gWeights.length; i++) {32
33
for (int j = 0; j < gWeights[0].length; j++) {34
35
if (gWeights[i][j] < Double.POSITIVE_INFINITY && i != j) { //means there is an edge between i and j36
37
paths[i][j] = i; //mark i as the predecessor of j to reach i38
39
} else {40
41
paths[i][j] = -1; //there is not edge, so mark -142
43
}44
45
}/**来 自 nowjava - 时 代 Java**/46
47
}48
49
//for every pair test if there is a shorter path gowing through another node50
51
for (int k = 0; k < gWeights.length; k++) {// test if ik->kj shorter than current i->j52
53
for (int i = 0; i < gWeights.length; i++) {54
55
for (int j = 0; j < gWeights.length; j++) { //pair i,j56
57
58
if (minDistances[i][j] > minDistances[i][k]59
60
+ minDistances[k][j]) {61
62
minDistances[i][j] = minDistances[i][k]63
64
+ minDistances[k][j];65
66
paths[i][j] = paths[k][j]; //the predecessor of j to reach i is the predecessor of j to reach k67
68
}69
70
}71
72
}73
74
}75
76
//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 null77
78
for (int i = 0; i < minDistances.length; i++) {79
80
if (minDistances[i][i] != 0) {81
82
return null; //there is a negative cycle in the graph83
84
}85
86
}87
88
return minDistances;89
90
}91
92
93
public static void main(String[] args) {94
95
double[][] gWeights = new double[][] {96
97
{ 0, 3, 6, 15 },98
99
{ Double.POSITIVE_INFINITY, 0, -2, Double.POSITIVE_INFINITY },100
101
{ Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, 2 },102
103
{ 1, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0 } };104
105
106
System.out.println("The weights matrix representing the graph :");107
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java