【引用】迪杰斯特拉(dijkstra)算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。
它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。
基本思想
通過(guò)dijkstra計(jì)算圖g中的最短路徑時(shí)，需要指定起點(diǎn)s(即從頂點(diǎn)s開(kāi)始計(jì)算)。
此外，引進(jìn)兩個(gè)集合s和u。s的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長(zhǎng)度)，而u則是記錄還未求出最短路徑的頂點(diǎn)(以及該頂點(diǎn)到起點(diǎn)s的距離)。
初始時(shí)，s中只有起點(diǎn)s；u中是除s之外的頂點(diǎn)，并且u中頂點(diǎn)的路徑是"起點(diǎn)s到該頂點(diǎn)的路徑"。然后，從u中找出路徑最短的頂點(diǎn)，并將其加入到s中；接著，更新u中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 然后，再?gòu)膗中找出路徑最短的頂點(diǎn)，并將其加入到s中；接著，更新u中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 ... 重復(fù)該操作，直到遍歷完所有頂點(diǎn)。
操作步驟
(1) 初始時(shí)，s只包含起點(diǎn)s；u包含除s外的其他頂點(diǎn)，且u中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離"[例如，u中頂點(diǎn)v的距離為(s,v)的長(zhǎng)度，然后s和v不相鄰，則v的距離為∞]。
(2) 從u中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到s中；同時(shí)，從u中移除頂點(diǎn)k。
(3) 更新u中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新u中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。
(4) 重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)。
得益于csdn另外一篇博客的算法，我對(duì)此做了一些改進(jìn)。
構(gòu)建地圖:
|
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é)點(diǎn)主鍵 */public class maps<t> { /** * 所有的節(jié)點(diǎn)集合 * 節(jié)點(diǎn)id - 節(jié)點(diǎn) */ private map<t, node<t>> nodes = new hashmap<t, node<t>>(); /** * 地圖構(gòu)建器 * * @author jake * @date 2014-7-26-下午9:47:44 */ public static class mapbuilder<t> { /** * map實(shí)例 */ private maps<t> map = new maps<t>(); /** * 構(gòu)造mapbuilder * * @return mapbuilder */ public mapbuilder<t> create() { return new mapbuilder<t>(); } /** * 添加節(jié)點(diǎn) * * @param node 節(jié)點(diǎn) * @return */ public mapbuilder<t> addnode(node<t> node) { map.nodes.put(node.getid(), node); return this; } /** * 添加路線 * * @param node1id 節(jié)點(diǎn)id * @param node2id 節(jié)點(diǎn)id * @param weight 權(quán)重 * @return */ public mapbuilder<t> addpath(t node1id, t node2id, int weight) { node<t> node1 = map.nodes.get(node1id); if (node1 == null) { throw new runtimeexception("無(wú)法找到節(jié)點(diǎn):" + node1id); } node<t> node2 = map.nodes.get(node2id); if (node2 == null) { throw new runtimeexception("無(wú)法找到節(jié)點(diǎn):" + node2id); } node1.getchilds().put(node2, weight); node2.getchilds().put(node1, weight); return this; } /** * 構(gòu)建map * @return map */ public maps<t> build() { return this.map; } } /** * 節(jié)點(diǎn) * * @author jake * @date 2014-7-26-下午9:51:31 * @param <t> 節(jié)點(diǎn)主鍵類型 */ public static class node<t> { /** * 節(jié)點(diǎn)主鍵 */ private t id; /** * 節(jié)點(diǎn)聯(lián)通路徑 * 相連節(jié)點(diǎn) - 權(quán)重 */ private map<node<t>, integer> childs = new hashmap<node<t>, integer>(); /** * 構(gòu)造方法 * @param id 節(jié)點(diǎn)主鍵 */ public node(t id) { this.id = id; } /** * 獲取實(shí)例 * @param id 主鍵 * @return */ public static <t> node<t> valueof(t id) { return new node<t>(id); } /** * 是否有效 * 用于動(dòng)態(tài)變化節(jié)點(diǎn)的可用性 * @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(); } } /** * 獲取地圖的無(wú)向圖節(jié)點(diǎn) * @return 節(jié)點(diǎn)id - 節(jié)點(diǎn) */ public map<t, node<t>> getnodes() { return nodes; } } |
開(kāi)始尋路:
|
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/>每次開(kāi)始新的搜索需要?jiǎng)?chuàng)建此類對(duì)象 * @param <t> 節(jié)點(diǎn)的主鍵類型 * @author jake * @date 2014-7-26-下午9:45:07 */public class mapsearcher<t> { /** * 最短路徑搜索結(jié)果類 * @author jake * @date 2014-7-27-下午3:55:11 * @param <t> 節(jié)點(diǎn)的主鍵類型 */ public static class searchresult<t> { /** * 最短路徑結(jié)果 */ list<t> path; /** * 最短距離 */ integer distance; /** * 獲取實(shí)例 * @param path 最短路徑結(jié)果 * @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(); } } /** * 地圖對(duì)象 */ maps<t> map; /** * 開(kāi)始節(jié)點(diǎn) */ maps.node<t> startnode; /** * 結(jié)束節(jié)點(diǎn) */ maps.node<t> targetnode; /** * 開(kāi)放的節(jié)點(diǎn) */ set<maps.node<t>> open = new hashset<maps.node<t>>(); /** * 關(guān)閉的節(jié)點(diǎn) */ 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>>(); /** * 初始化起始點(diǎn) * <br/>初始時(shí)，s只包含起點(diǎn)s；u包含除s外的其他頂點(diǎn)，且u中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離" * [例如，u中頂點(diǎn)v的距離為(s,v)的長(zhǎng)度，然后s和v不相鄰，則v的距離為∞]。 * @param source 起始節(jié)點(diǎn)的id * @param map 全局地圖 * @param closeset 已經(jīng)關(guān)閉的節(jié)點(diǎn)列表 * @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é)點(diǎn)放到close close.add(startnode); //將其他節(jié)點(diǎn)放到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é)點(diǎn) */ protected void computepath(maps.node<t> start) { // 從u中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到s中；同時(shí)，從u中移除頂點(diǎn)k。 maps.node<t> nearest = getshortestpath(start); if (nearest == null) { return; } //更新u中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。 //之所以更新u中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離； //例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。 close.add(nearest); open.remove(nearest); //已經(jīng)找到結(jié)果 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é)點(diǎn)在open中 integer newcompute = path.get(nearest) + childs.get(child); if (path.get(child) > newcompute) {// 之前設(shè)置的距離大于新計(jì)算出來(lái)的距離 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);// 重復(fù)執(zhí)行自己,確保所有子節(jié)點(diǎn)被遍歷 computepath(nearest);// 向外一層層遞歸,直至所有頂點(diǎn)被遍歷 } /** * 獲取與node最近的子節(jié)點(diǎn) */ 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; } /** * 獲取到目標(biāo)點(diǎn)的最短路徑 * * @param target * 目標(biāo)點(diǎn) * @return */ public searchresult<t> getresult(t target) { maps.node<t> targetnode = this.map.getnodes().get(target); if(targetnode == null) { throw new runtimeexception("目標(biāo)節(jié)點(diǎn)不存在!"); } this.targetnode = targetnode; //開(kāi)始計(jì)算 this.computepath(startnode); return searchresult.valueof(pathinfo.get(target), path.get(targetnode)); } /** * 打印出所有點(diǎn)的最短路徑 */ 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()); } } /** * 測(cè)試方法 */ @org.junit.test public void test() { mapbuilder<string> mapbuilder = new maps.mapbuilder<string>().create(); //構(gòu)建節(jié)點(diǎn) 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")); //構(gòu)建路徑 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); //構(gòu)建全局map maps<string> map = mapbuilder.build(); //創(chuàng)建路徑搜索器(每次搜索都需要?jiǎng)?chuàng)建新的mapsearcher) mapsearcher<string> searcher = new mapsearcher<string>(); //創(chuàng)建關(guān)閉節(jié)點(diǎn)集合 set<string> closenodeidsset = new hashset<string>(); closenodeidsset.add("c"); //設(shè)置初始節(jié)點(diǎn) searcher.init("a", map, closenodeidsset); //獲取結(jié)果 searchresult<string> result = searcher.getresult("g"); system.out.println(result); //test.printpathinfo(); } } |
根據(jù)算法的原理可知，getshortestpath是獲取open集合里面目前更新的距離離起始點(diǎn)最短路徑的節(jié)點(diǎn)。基于廣度優(yōu)先原則，可以避免路徑權(quán)重不均導(dǎo)致錯(cuò)尋的情況。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/jake_gogo/article/details/38175137
