class="Apple-style-span" style="font-family: verdana, arial, helvetica, sans-serif; line-height: 19.5px;">【引用】迪杰斯特拉(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另外一篇博客的算法,我对此做了一些改进。http://blog.csdn.net/javaman_chen/article/details/8254309
构建地图:
?
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; } }
?
开始寻路:
?
?
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集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则,可以避免路径权重不均导致错寻的情况。