【引用】迪杰斯特拉(dijkstra)算法是典型最短路徑算法，用于計算一個節(jié)點到其他節(jié)點的最短路徑。
它的主要特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想)，直到擴展到終點為止。
基本思想
通過dijkstra計算圖g中的最短路徑時，需要指定起點s(即從頂點s開始計算)。
此外，引進兩個集合s和u。s的作用是記錄已求出最短路徑的頂點(以及相應的最短路徑長度)，而u則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)。
初始時，s中只有起點s；u中是除s之外的頂點，并且u中頂點的路徑是"起點s到該頂點的路徑"。然后，從u中找出路徑最短的頂點，并將其加入到s中；接著，更新u中的頂點和頂點對應的路徑。 然后，再從u中找出路徑最短的頂點，并將其加入到s中；接著，更新u中的頂點和頂點對應的路徑。 ... 重復該操作，直到遍歷完所有頂點。
操作步驟
(1) 初始時，s只包含起點s；u包含除s外的其他頂點，且u中頂點的距離為"起點s到該頂點的距離"[例如，u中頂點v的距離為(s,v)的長度，然后s和v不相鄰，則v的距離為∞]。
(2) 從u中選出"距離最短的頂點k"，并將頂點k加入到s中；同時，從u中移除頂點k。
(3) 更新u中各個頂點到起點s的距離。之所以更新u中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。
(4) 重復步驟(2)和(3)，直到遍歷完所有頂點。
得益于csdn另外一篇博客的算法，我對此做了一些改進。
構建地圖:
|
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
|
import java.util.hashmap;import java.util.iterator;import java.util.map;import java.util.map.entry; /** * 地圖 * @author jake * @date 2014-7-26-下午10:40:10 * @param <t> 節(jié)點主鍵 */public class maps<t> { /** * 所有的節(jié)點集合 * 節(jié)點id - 節(jié)點 */ private map<t, node<t>> nodes = new hashmap<t, node<t>>(); /** * 地圖構建器 * * @author jake * @date 2014-7-26-下午9:47:44 */ public static class mapbuilder<t> { /** * map實例 */ private maps<t> map = new maps<t>(); /** * 構造mapbuilder * * @return mapbuilder */ public mapbuilder<t> create() { return new mapbuilder<t>(); } /** * 添加節(jié)點 * * @param node 節(jié)點 * @return */ public mapbuilder<t> addnode(node<t> node) { map.nodes.put(node.getid(), node); return this; } /** * 添加路線 * * @param node1id 節(jié)點id * @param node2id 節(jié)點id * @param weight 權重 * @return */ public mapbuilder<t> addpath(t node1id, t node2id, int weight) { node<t> node1 = map.nodes.get(node1id); if (node1 == null) { throw new runtimeexception("無法找到節(jié)點:" + node1id); } node<t> node2 = map.nodes.get(node2id); if (node2 == null) { throw new runtimeexception("無法找到節(jié)點:" + node2id); } node1.getchilds().put(node2, weight); node2.getchilds().put(node1, weight); return this; } /** * 構建map * @return map */ public maps<t> build() { return this.map; } } /** * 節(jié)點 * * @author jake * @date 2014-7-26-下午9:51:31 * @param <t> 節(jié)點主鍵類型 */ public static class node<t> { /** * 節(jié)點主鍵 */ private t id; /** * 節(jié)點聯(lián)通路徑 * 相連節(jié)點 - 權重 */ private map<node<t>, integer> childs = new hashmap<node<t>, integer>(); /** * 構造方法 * @param id 節(jié)點主鍵 */ public node(t id) { this.id = id; } /** * 獲取實例 * @param id 主鍵 * @return */ public static <t> node<t> valueof(t id) { return new node<t>(id); } /** * 是否有效 * 用于動態(tài)變化節(jié)點的可用性 * @return */ public boolean validate() { return true; } public t getid() { return id; } public void setid(t id) { this.id = id; } public map<node<t>, integer> getchilds() { return childs; } protected void setchilds(map<node<t>, integer> childs) { this.childs = childs; } @override public string tostring() { stringbuilder sb = new stringbuilder(); sb.append(this.id).append("["); for (iterator<entry<node<t>, integer>> it = childs.entryset().iterator(); it.hasnext();) { entry<node<t>, integer> next = it.next(); sb.append(next.getkey().getid()).append("=").append(next.getvalue()); if (it.hasnext()) { sb.append(","); } } sb.append("]"); return sb.tostring(); } } /** * 獲取地圖的無向圖節(jié)點 * @return 節(jié)點id - 節(jié)點 */ public map<t, node<t>> getnodes() { return nodes; } } |
開始尋路:
|
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
|
import java.util.arraylist;import java.util.arrays;import java.util.hashmap;import java.util.hashset;import java.util.iterator;import java.util.list;import java.util.map;import java.util.map.entry;import java.util.set; import com.my9yu.sanguohun2.utils.dijkstra.maps.mapbuilder; /** * 迪杰斯特拉(dijkstra)圖最短路徑搜索算法 * <br/>每次開始新的搜索需要創(chuàng)建此類對象 * @param <t> 節(jié)點的主鍵類型 * @author jake * @date 2014-7-26-下午9:45:07 */public class mapsearcher<t> { /** * 最短路徑搜索結果類 * @author jake * @date 2014-7-27-下午3:55:11 * @param <t> 節(jié)點的主鍵類型 */ public static class searchresult<t> { /** * 最短路徑結果 */ list<t> path; /** * 最短距離 */ integer distance; /** * 獲取實例 * @param path 最短路徑結果 * @param distance 最短路徑距離 * @return */ protected static <t> searchresult<t> valueof(list<t> path, integer distance) { searchresult<t> r = new searchresult<t>(); r.path = path; r.distance = distance; return r; } public list<t> getpath() { return path; } public integer getdistance() { return distance; } @override public string tostring() { stringbuffer sb = new stringbuffer(); sb.append("path:"); for(iterator<t> it = this.path.iterator(); it.hasnext();) { sb.append(it.next()); if(it.hasnext()) { sb.append("->"); } } sb.append("\n").append("distance:").append(distance); return sb.tostring(); } } /** * 地圖對象 */ maps<t> map; /** * 開始節(jié)點 */ maps.node<t> startnode; /** * 結束節(jié)點 */ maps.node<t> targetnode; /** * 開放的節(jié)點 */ set<maps.node<t>> open = new hashset<maps.node<t>>(); /** * 關閉的節(jié)點 */ set<maps.node<t>> close = new hashset<maps.node<t>>(); /** * 最短路徑距離 */ map<maps.node<t>, integer> path = new hashmap<maps.node<t>, integer>(); /** * 最短路徑 */ map<t, list<t>> pathinfo = new hashmap<t, list<t>>(); /** * 初始化起始點 * <br/>初始時，s只包含起點s；u包含除s外的其他頂點，且u中頂點的距離為"起點s到該頂點的距離" * [例如，u中頂點v的距離為(s,v)的長度，然后s和v不相鄰，則v的距離為∞]。 * @param source 起始節(jié)點的id * @param map 全局地圖 * @param closeset 已經(jīng)關閉的節(jié)點列表 * @return */ @suppresswarnings("unchecked") public maps.node<t> init(t source, maps<t> map, set<t> closeset) { map<t, maps.node<t>> nodemap = map.getnodes(); maps.node<t> startnode = nodemap.get(source); //將初始節(jié)點放到close close.add(startnode); //將其他節(jié)點放到open for(maps.node<t> node : nodemap.values()) { if(!closeset.contains(node.getid()) && !node.getid().equals(source)) { this.open.add(node); } } // 初始路徑 t startnodeid = startnode.getid(); for(entry<maps.node<t>, integer> entry : startnode.getchilds().entryset()) { maps.node<t> node = entry.getkey(); if(open.contains(node)) { t nodeid = node.getid(); path.put(node, entry.getvalue()); pathinfo.put(nodeid, new arraylist<t>(arrays.aslist(startnodeid, nodeid))); } } for(maps.node<t> node : nodemap.values()) { if(open.contains(node) && !path.containskey(node)) { path.put(node, integer.max_value); pathinfo.put(node.getid(), new arraylist<t>(arrays.aslist(startnodeid))); } } this.startnode = startnode; this.map = map; return startnode; } /** * 遞歸dijkstra * @param start 已經(jīng)選取的最近節(jié)點 */ protected void computepath(maps.node<t> start) { // 從u中選出"距離最短的頂點k"，并將頂點k加入到s中；同時，從u中移除頂點k。 maps.node<t> nearest = getshortestpath(start); if (nearest == null) { return; } //更新u中各個頂點到起點s的距離。 //之所以更新u中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離； //例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。 close.add(nearest); open.remove(nearest); //已經(jīng)找到結果 if(nearest == this.targetnode) { return; } map<maps.node<t>, integer> childs = nearest.getchilds(); for (maps.node<t> child : childs.keyset()) { if (open.contains(child)) {// 如果子節(jié)點在open中 integer newcompute = path.get(nearest) + childs.get(child); if (path.get(child) > newcompute) {// 之前設置的距離大于新計算出來的距離 path.put(child, newcompute); list<t> path = new arraylist<t>(pathinfo.get(nearest.getid())); path.add(child.getid()); pathinfo.put(child.getid(), path); } } }// computepath(start);// 重復執(zhí)行自己,確保所有子節(jié)點被遍歷 computepath(nearest);// 向外一層層遞歸,直至所有頂點被遍歷 } /** * 獲取與node最近的子節(jié)點 */ private maps.node<t> getshortestpath(maps.node<t> node) { maps.node<t> res = null; int mindis = integer.max_value; for (maps.node<t> entry : path.keyset()) { if (open.contains(entry)) { int distance = path.get(entry); if (distance < mindis) { mindis = distance; res = entry; } } } return res; } /** * 獲取到目標點的最短路徑 * * @param target * 目標點 * @return */ public searchresult<t> getresult(t target) { maps.node<t> targetnode = this.map.getnodes().get(target); if(targetnode == null) { throw new runtimeexception("目標節(jié)點不存在!"); } this.targetnode = targetnode; //開始計算 this.computepath(startnode); return searchresult.valueof(pathinfo.get(target), path.get(targetnode)); } /** * 打印出所有點的最短路徑 */ public void printpathinfo() { set<map.entry<t, list<t>>> pathinfos = pathinfo.entryset(); for (map.entry<t, list<t>> pathinfo : pathinfos) { system.out.println(pathinfo.getkey() + ":" + pathinfo.getvalue()); } } /** * 測試方法 */ @org.junit.test public void test() { mapbuilder<string> mapbuilder = new maps.mapbuilder<string>().create(); //構建節(jié)點 mapbuilder.addnode(maps.node.valueof("a")); mapbuilder.addnode(maps.node.valueof("b")); mapbuilder.addnode(maps.node.valueof("c")); mapbuilder.addnode(maps.node.valueof("d")); mapbuilder.addnode(maps.node.valueof("e")); mapbuilder.addnode(maps.node.valueof("f")); mapbuilder.addnode(maps.node.valueof("g")); mapbuilder.addnode(maps.node.valueof("h")); mapbuilder.addnode(maps.node.valueof("i")); //構建路徑 mapbuilder.addpath("a", "b", 1); mapbuilder.addpath("a", "f", 2); mapbuilder.addpath("a", "d", 4); mapbuilder.addpath("a", "c", 1); mapbuilder.addpath("a", "g", 5); mapbuilder.addpath("c", "g", 3); mapbuilder.addpath("g", "h", 1); mapbuilder.addpath("h", "b", 4); mapbuilder.addpath("b", "f", 2); mapbuilder.addpath("e", "f", 1); mapbuilder.addpath("d", "e", 1); mapbuilder.addpath("h", "i", 1); mapbuilder.addpath("c", "i", 1); //構建全局map maps<string> map = mapbuilder.build(); //創(chuàng)建路徑搜索器(每次搜索都需要創(chuàng)建新的mapsearcher) mapsearcher<string> searcher = new mapsearcher<string>(); //創(chuàng)建關閉節(jié)點集合 set<string> closenodeidsset = new hashset<string>(); closenodeidsset.add("c"); //設置初始節(jié)點 searcher.init("a", map, closenodeidsset); //獲取結果 searchresult<string> result = searcher.getresult("g"); system.out.println(result); //test.printpathinfo(); } } |
根據(jù)算法的原理可知，getshortestpath是獲取open集合里面目前更新的距離離起始點最短路徑的節(jié)點。基于廣度優(yōu)先原則，可以避免路徑權重不均導致錯尋的情況。
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/jake_gogo/article/details/38175137
