摘要: 算法導論之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
