## 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; } ~~~