【引用】迪杰斯特拉(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 测试数据putepath(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
查看更多关于java实现dijkstra最短路径寻路算法的详细内容...