## Dijkstra算法 Dijkstra算法是用于计算图里单元内某个顶点到其他顶点的最小路径的算法。 适用于边全职没有累加为负数的环的图。 ### 算法描述 dijkstra算法求单元最小路径,适用范围：没有累加为负数的环 1. 初始化路径表distanceMap,from顶点到各个顶点的距离 2. 在路径表distanceMap找没有被锁定（不在lockSet)的最小顶点 3. 最小顶点不为空，则处理最小顶点的相邻边，记录边的to顶点的最小距离到记录表里 4. 处理完后将最小顶点加入到lockSet里锁定 5. 找下一个最小顶点，循环步骤3执行 ### 步骤图解析  ### Java代码实现 ~~~ /** * dijkstra算法求单元最小路径,适用范围：没有累加为负数的环 * 1. 初始化路径表distanceMap,from顶点到各个顶点的距离 * 2. 在路径表distanceMap找没有被锁定（不在lockSet)的最小顶点 * 3. 最小顶点不为空，则处理最小顶点的相邻边，记录边的to顶点的最小距离到记录表里 * 4. 处理完后将最小顶点加入到lockSet里锁定 * 5. 找下一个最小顶点，循环步骤3执行 * @param from 开始顶点 * @return key=顶点，value=from顶点到各个顶点的最小路径 */ public Map<Vertex,Integer> dijkstra(Vertex from){ // 记录最小路径的map Map<Vertex,Integer> distanceMap = new LinkedHashMap<>(); // 记录自己为零 distanceMap.put(from,0); Set<Vertex> lockSet = new HashSet<>(); // 在distanceMap里找到未被锁定的的最小路径的顶点 Vertex theMin = findMin(distanceMap,lockSet); while(theMin != null){ // 原来记录的最小路径 Integer distance = distanceMap.get(theMin); // 处理最小顶点的边 for(Edge edge : theMin.edges){ // edge.to顶点没有被记录在distanceMap里的 if(!distanceMap.containsKey(edge.to)){ distanceMap.put(edge.to,distance + edge.weight); }else{ // 已经记录的则更新最小值 distanceMap.put(edge.to,Math.min(distanceMap.get(edge.to),distance + edge.weight)); } } // 处理完最小顶点的相邻边后，加入锁定 lockSet.add(theMin); // 继续找下一个最小顶点处理 theMin = findMin(distanceMap,lockSet); } return distanceMap; } ~~~ ~~~ /** * 在distanceMap里找到未被锁定的（不在lockSet)里的最小路径的顶点 * @param distanceMap 路径记录表 * @param lockSet 锁定的顶点集合 * @return 路径最小的点 */ private Vertex findMin(Map<Vertex, Integer> distanceMap, Set<Vertex> lockSet) { Vertex vertex = null; int min = Integer.MAX_VALUE; for(Vertex v : distanceMap.keySet()){ if(!lockSet.contains(v) && min > distanceMap.get(v)){ vertex = v; min = distanceMap.get(v); } } return vertex; } ~~~