个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
27
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章java算法导论之FloydWarshall算法实现代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
摘要: 算法导论之FloydWarshall算法 。
求一个图中任意两点之间的最短路径 。
|
1
2
3
4
5
6
|
FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径
如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^
2
如果是稀疏图，则近似于V^
3
但是如果是密集图，则时间复杂度会近似达到V^
4
，这种情况需要优化，这里FloydWarshall通过动态规划进行优化
，并且使用邻接矩阵来表示图。
|
实例代码:
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
package
org.loda.graph;
import
java.math.BigDecimal;
import
java.math.RoundingMode;
import
org.loda.util.In;
/**
*
* @ClassName: FloydWarshall
* @Description: 求一个图中任意两点之间的最短路径
*
* FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径
*
* 如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^2
* 如果是稀疏图，则近似于V^3
* 但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化
* ，并且使用邻接矩阵来表示图。
* d(i,j); if m=0
* D(i,j,m)={
* min(D(i,m,m-1)+D(m,j,m-1),D(i,j,m-1)); if m!=0
* @author minjun
* @date 2015年6月1日 上午9:39:42
*
*/
public
class
FloydWarshall {
private
double
[][] d;
private
int
[][] prev;
private
int
v;
private
boolean
negativeCycle;
public
FloydWarshall(
int
v) {
this
.v = v;
d =
new
double
[v][v];
prev =
new
int
[v][v];
// 默认设置所有节点都不可达，而自己到自己是可达并且距离为0.0
for
(
int
i =
0
; i < v; i++) {
for
(
int
j =
0
; j < v; j++) {
d[i][j] = Double.POSITIVE_INFINITY;
prev[i][j] = -
1
;
if
(i==j){
d[i][j] =
0
;
}
}
}
}
/**
*
* @Title: findShortestPath
* @Description: 查询最短路径
* @param 设定文件
* @return void 返回类型
* @throws
*/
public
void
findShortestPath() {
//查找最短路径
for
(
int
k =
0
; k < v; k++) {
//将每个k值考虑成i->j路径中的一个中间点
for
(
int
i =
0
; i < v; i++) {
for
(
int
j =
0
; j < v; j++) {
//如果存在使得权重和更小的中间值k，就更新最短路径为经过k的路径
if
(d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
prev[i][j]=k;
}
}
}
}
//四舍五入距离
for
(
int
i =
0
; i < v; i++) {
for
(
int
j =
0
; j < v; j++) {
d[i][j] =
new
BigDecimal(d[i][j]).setScale(
2
,
RoundingMode.HALF_UP).doubleValue();
}
}
//检测负权重环的方式很简单，就是判断所有i->i的距离d[i][i]，如果存在小于0的，表示这个i->i的环路的权重和形成了一个负值，也就是存在这个负权重
//在之前的其他最短路径算法中，无法通过这个方法来检测负环，因为之前路径距离都是保存在一个一维数组中，相等于只能检测d[0][0]，无法检测每个d[i][i]
for
(
int
i=
0
;i<v;i++){
if
(d[i][i]<
0
)
negativeCycle=
true
;
}
}
/**
*
* @Title: hasNegativeCycle
* @Description: 是否拥有负权重环
* @param @return 设定文件
* @return boolean 返回类型
* @throws
*/
public
boolean
hasNegativeCycle() {
return
negativeCycle;
}
/**
*
* @Title: distTo
* @Description: a->b最短路径的距离
* @param @param a
* @param @param b
* @param @return 设定文件
* @return double 返回类型
* @throws
*/
public
double
distTo(
int
a,
int
b) {
if
(hasNegativeCycle())
throw
new
RuntimeException(
"有负权重环，不存在最短路径"
);
return
d[a][b];
}
/**
*
* @Title: printShortestPath
* @Description: 打印a->b最短路径
* @param @return 设定文件
* @return Iterable<Integer> 返回类型
* @throws
*/
public
boolean
printShortestPath(
int
a,
int
b){
if
(hasNegativeCycle()){
System.out.print(
"有负权重环，不存在最短路径"
);
}
else
if
(a==b)
System.out.println(a+
"->"
+b);
else
{
System.out.print(a+
"->"
);
path(a,b);
System.out.print(b);
}
return
true
;
}
private
void
path(
int
a,
int
b) {
int
k=prev[a][b];
if
(k==-
1
){
return
;
}
path(a,k);
System.out.print(k+
"->"
);
path(k,b);
}
/**
*
* @Title: addEdge
* @Description: 添加边
* @param @param a
* @param @param b
* @param @param w 设定文件
* @return void 返回类型
* @throws
*/
public
void
addEdge(
int
a,
int
b,
double
w) {
d[a][b] = w;
}
public
static
void
main(String[] args) {
// 不含负权重环的文本数据
String text1 =
"F:\\算法\\attach\\tinyEWDn.txt"
;
// 含有负权重环的文本数据
String text2 =
"F:\\算法\\attach\\tinyEWDnc.txt"
;
In in =
new
In(text1);
int
n = in.readInt();
FloydWarshall f =
new
FloydWarshall(n);
int
e = in.readInt();
for
(
int
i =
0
; i < e; i++) {
f.addEdge(in.readInt(), in.readInt(), in.readDouble());
}
f.findShortestPath();
int
s =
0
;
for
(
int
i =
0
; i < n; i++) {
System.out.println(s +
"到"
+ i +
"的距离为:"
+ f.distTo(s, i));
f.printShortestPath(s, i);
System.out.println();
}
}
}
|
如果采用负权重环图，则会抛出异常，提示负环并表示无最短路径 。
如果采用不含负环的图，则会打印如下内容（目前以s=0作测试，其他点作为原点的最短路径可以自行尝试）:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
0
到
0
的距离为:
0.0
0
->
0
0
到
1
的距离为:
0.93
0
->
2
->
7
->
3
->
6
->
4
->
5
->
1
0
到
2
的距离为:
0.26
0
->
2
0
到
3
的距离为:
0.99
0
->
2
->
7
->
3
0
到
4
的距离为:
0.26
0
->
2
->
7
->
3
->
6
->
4
0
到
5
的距离为:
0.61
0
->
2
->
7
->
3
->
6
->
4
->
5
0
到
6
的距离为:
1.51
0
->
2
->
7
->
3
->
6
0
到
7
的距离为:
0.6
0
->
2
->
7
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持.
原文链接：https://my.oschina.net/u/1378920/blog/423862 。
最后此篇关于java算法导论之FloydWarshall算法实现代码的文章就讲到这里了,如果你想了解更多关于java算法导论之FloydWarshall算法实现代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
我是一名优秀的程序员,十分优秀！