【引用】迪杰斯特拉(dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
基本思想
通过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> 节点主键 */public class maps<t> { /** * 所有的节点集合 * 节点id - 节点 */ 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>(); } /** * 添加节点 * * @param node 节点 * @return */ public mapbuilder<t> addnode(node<t> node) { map.nodes.put(node.getid(), node); return this; } /** * 添加路线 * * @param node1id 节点id * @param node2id 节点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("无法找到节点:" + node1id); } node<t> node2 = map.nodes.get(node2id); if (node2 == null) { throw new runtimeexception("无法找到节点:" + node2id); } node1.getchilds().put(node2, weight); node2.getchilds().put(node1, weight); return this; } /** * 构建map * @return map */ public maps<t> build() { return this.map; } } /** * 节点 * * @author jake * @date 2014-7-26-下午9:51:31 * @param <t> 节点主键类型 */ public static class node<t> { /** * 节点主键 */ private t id; /** * 节点联通路径 * 相连节点 - 权重 */ private map<node<t>, integer> childs = new hashmap<node<t>, integer>(); /** * 构造方法 * @param id 节点主键 */ public node(t id) { this.id = id; } /** * 获取实例 * @param id 主键 * @return */ public static <t> node<t> valueof(t id) { return new node<t>(id); } /** * 是否有效 * 用于动态变化节点的可用性 * @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(); } } /** * 获取地图的无向图节点 * @return 节点id - 节点 */ 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/>每次开始新的搜索需要创建此类对象 * @param <t> 节点的主键类型 * @author jake * @date 2014-7-26-下午9:45:07 */public class mapsearcher<t> { /** * 最短路径搜索结果类 * @author jake * @date 2014-7-27-下午3:55:11 * @param <t> 节点的主键类型 */ 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; /** * 开始节点 */ maps.node<t> startnode; /** * 结束节点 */ maps.node<t> targetnode; /** * 开放的节点 */ set<maps.node<t>> open = new hashset<maps.node<t>>(); /** * 关闭的节点 */ 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 起始节点的id * @param map 全局地图 * @param closeset 已经关闭的节点列表 * @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); //将初始节点放到close close.add(startnode); //将其他节点放到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 已经选取的最近节点 */ 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); //已经找到结果 if(nearest == this.targetnode) { return; } map<maps.node<t>, integer> childs = nearest.getchilds(); for (maps.node<t> child : childs.keyset()) { if (open.contains(child)) {// 如果子节点在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);// 重复执行自己,确保所有子节点被遍历 computepath(nearest);// 向外一层层递归,直至所有顶点被遍历 } /** * 获取与node最近的子节点 */ 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("目标节点不存在!"); } 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(); //构建节点 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(); //创建路径搜索器(每次搜索都需要创建新的mapsearcher) mapsearcher<string> searcher = new mapsearcher<string>(); //创建关闭节点集合 set<string> closenodeidsset = new hashset<string>(); closenodeidsset.add("c"); //设置初始节点 searcher.init("a", map, closenodeidsset); //获取结果 searchresult<string> result = searcher.getresult("g"); system.out.println(result); //test.printpathinfo(); } } |
根据算法的原理可知，getshortestpath是获取open集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则，可以避免路径权重不均导致错寻的情况。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/jake_gogo/article/details/38175137
