1. /**
    2.  * dijkstra 单元最短路径算法
    3.  */
    4. // no negative weight
    5. public class Code06_Dijkstra {
    7.     /**
    8.      * 方式1.傻白甜版本
    9.      * 给一个节点，返回该点所能到达该点的最小路径和，到达不了的为正无穷
    10.      */
    11.     public static HashMap<Node, Integer> dijkstra1(Node from) {
    12.         // 距离表
    13.         HashMap<Node, Integer> distanceMap = new HashMap<>();
    14.         // 到自己的距离为0
    15.         distanceMap.put(from, 0);
    16.         // 打过对号的点
    17.         HashSet<Node> selectedNodes = new HashSet<>();
    18.         // 获取距离map表中未被选择最短据距离的节点，第一步调用必定是from，原始节点
    19.         Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
    20.         while (minNode != null) {
    21.             //  原始点  ->  minNode(跳转点)   原始点from到中转点minNode的最小距离distance
    22.             int distance = distanceMap.get(minNode);
    23.             // 考虑跳转点的所有边
    24.             for (Edge edge : minNode.edges) {
    25.                 Node toNode = edge.to;
    26.                 if (!distanceMap.containsKey(toNode)) { // toNode 不在distanceMap中，认为距离为正无穷
    27.                     distanceMap.put(toNode, distance + edge.weight);
    28.                 } else { // toNode 在distanceMap中进行比较，小的更新
    29.                     distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
    30.                 }
    31.             }
    32.             // 这个中转点结束
    33.             selectedNodes.add(minNode);
    34.             // 获取下一个中转点
    35.             minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
    36.         }
    37.         return distanceMap;
    38.     }
    39.     // 查找距离表中除被选择的节点之外的距离最短的节点
    40.     public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
    41.         Node minNode = null;
    42.         int minDistance = Integer.MAX_VALUE;
    43.         for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
    44.             Node node = entry.getKey();
    45.             int distance = entry.getValue();
    46.             if (!touchedNodes.contains(node) && distance < minDistance) {
    47.                 minNode = node;
    48.                 minDistance = distance;
    49.             }
    50.         }
    51.         return minNode;
    52.     }
    54.     // ################################以下是dijkstra优化方法###################################################
    56.     /**
    57.      * 方法2：优化，对每次查找距离表中的最小距离进行优化，getMinDistanceAndUnselectedNode这个方法。加强堆
    58.      * @param head
    59.      * @param size  图的节点个数
    60.      * @return
    61.      */
    62.     // 改进后的dijkstra算法
    63.     // 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
    64.     public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
    65.         NodeHeap nodeHeap = new NodeHeap(size);
    66.         // 堆中 add  update ignore 整合在一起
    67.         nodeHeap.addOrUpdateOrIgnore(head, 0); // logN
    68.         HashMap<Node, Integer> result = new HashMap<>();
    69.         while (!nodeHeap.isEmpty()) {
    70.             NodeRecord record = nodeHeap.pop();
    71.             Node cur = record.node;
    72.             int distance = record.distance;
    73.             for (Edge edge : cur.edges) {
    74.                 nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
    75.             }
    76.             result.put(cur, distance);
    77.         }
    78.         return result;
    79.     }
    81.     // 存放在加强堆中的节点封装，节点和当前到节点的距离
    82.     public static class NodeRecord {
    83.         public Node node;
    84.         public int distance;
    86.         public NodeRecord(Node node, int distance) {
    87.             this.node = node;
    88.             this.distance = distance;
    89.         }
    90.     }
    92.     // 加强堆  小根堆结构描述
    93.     public static class NodeHeap {
    94.         private Node[] nodes;                        // 正向索引，实际的堆结构
    95.         private HashMap<Node, Integer> heapIndexMap; // 反向索引表，根据节点找到节点所在的位置，key存节点value存放node的下标
    96.         private HashMap<Node, Integer> distanceMap;  // key 某一个节点， value 从源节点出发到该节点的目前最小距离
    97.         private int size; // 堆上有多少个点
    99.         public NodeHeap(int size) {
    100.             nodes = new Node[size];
    101.             heapIndexMap = new HashMap<>();
    102.             distanceMap = new HashMap<>();
    103.             size = 0;
    104.         }
    106.         public boolean isEmpty() {
    107.             return size == 0;
    108.         }
    110.         // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
    111.         // 判断要不要更新，如果需要的话，就更新
    112.         public void addOrUpdateOrIgnore(Node node, int distance) {
    113.             if (inHeap(node)) { // 如果在堆上，距离小进行更新
    114.                 distanceMap.put(node, Math.min(distanceMap.get(node), distance));
    115.                 insertHeapify(node, heapIndexMap.get(node)); // 向上调整
    116.             }
    117.             if (!isEntered(node)) {  // 表示没有进来过，表示堆中新增一个节点
    118.                 nodes[size] = node;
    119.                 heapIndexMap.put(node, size);
    120.                 distanceMap.put(node, distance);
    121.                 insertHeapify(node, size++);
    122.             }
    123.             // 既没有在堆上也不是第一次进堆，ignore操作，不做任何操作。
    124.         }
    126.         // 弹出堆顶元素
    127.         public NodeRecord pop() {
    128.             NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
    129.             swap(0, size - 1);
    130.             heapIndexMap.put(nodes[size - 1], -1);
    131.             distanceMap.remove(nodes[size - 1]);
    132.             // free C++同学还要把原本堆顶节点析构，对java同学不必
    133.             nodes[size - 1] = null;
    134.             heapify(0, --size);
    135.             return nodeRecord;
    136.         }
    138.         private void insertHeapify(Node node, int index) {
    139.             while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
    140.                 swap(index, (index - 1) / 2);
    141.                 index = (index - 1) / 2;
    142.             }
    143.         }
    145.         private void heapify(int index, int size) {
    146.             int left = index * 2 + 1;
    147.             while (left < size) {
    148.                 int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
    149.                         ? left + 1
    150.                         : left;
    151.                 smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
    152.                 if (smallest == index) {
    153.                     break;
    154.                 }
    155.                 swap(smallest, index);
    156.                 index = smallest;
    157.                 left = index * 2 + 1;
    158.             }
    159.         }
    161.         // 判断一个节点是否进去过堆
    162.         private boolean isEntered(Node node) {
    163.             return heapIndexMap.containsKey(node);
    164.         }
    166.         // headIndexMap value值为-1 表示node进出过依次堆，为已经找到最小路径的节点，不在操纵。
    167.         private boolean inHeap(Node node) {
    168.             return isEntered(node) && heapIndexMap.get(node) != -1;
    169.         }
    171.         // 堆交换的同时保持反向索引表同步更新
    172.         private void swap(int index1, int index2) {
    173.             heapIndexMap.put(nodes[index1], index2);
    174.             heapIndexMap.put(nodes[index2], index1);
    175.             Node tmp = nodes[index1];
    176.             nodes[index1] = nodes[index2];
    177.             nodes[index2] = tmp;
    178.         }
    179.     }
    180. }