摘要: 算法导论之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.00->00到1的距离为:0.930->2->7->3->6->4->5->10到2的距离为:0.260->20到3的距离为:0.990->2->7->30到4的距离为:0.260->2->7->3->6->40到5的距离为:0.610->2->7->3->6->4->50到6的距离为:1.510->2->7->3->60到7的距离为:0.60->2->7 |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持!
原文链接：https://my.oschina.net/u/1378920/blog/423862
