迪杰斯特拉

概念：

是从一个顶点到其余各顶点的最短路径的算法，解决的是有向图中最短路径问题。

思路：

自定义数据结构NodeHeap小根堆，小根堆的每个位置上的值是当前结点和到原点距离的封装的一个数据，根据到原点的距离来实现小根堆，NodeHeap里有nodes[]，看成堆数组（即数组结构看成堆，数组的下标对应在堆中的位置），heapIndexMap<Node，Integer>用来记录当前结点在堆中的位置，distanceMap（用来记录当前结点和到原点的距离），以及size堆的初始大小。
NodeHeap中有如下方法：
isEmpty（）判断堆是否为空；
isEntered（）当前结点是否进入过小根堆；
inHeap（）当前结点是否还在小根堆中；只有进入过小根堆且，heapIndexMap的index值不是-1时才说明在小根堆，index=-1代表当前结点已经弹出；
heapify（）堆排序的下沉过程，其中注意传进来的参数一个是当前结点的下标，另一个是当前堆的大小；
heapInsert（）堆排序建立小根堆的过程，这里注意传进来的参数是当前结点和当前结点的小标，比较通过distanceMap.get（nodes[index]）来获取当前结点到原点的距离比较；
addOrUpdateOrIgnore（）插入节点的过程，如果当前结点没有进入过小根堆就直接加，如果在堆中，就更新小根堆的数据，在这里会出现如下图情况

image.png

如图第一次加数据时B到原点的权值是8，当加入A点后解锁了3的权值路径被解锁，此时原点到B的最小路径是5，所以就要执行更新数据的过程了。
pop（）方法，将小根堆堆顶即当前所有节点中到原点距离最小的节点的值弹出，以解锁其它路径等。
总之迪杰斯特拉此实现方法的整体概括是：利用自定义小根堆来简化找最小路径的过程，通过不断弹出已解锁的最小节点路径，来解锁它后序节点，更新最短路径来实现。

以上图为例，解释迪杰斯特拉的过程，最开始是把上图0节点先加入到堆中，遍历他的后序节点A，B，把A,B加入到小根堆，然后因为A的权值小于B，A称为小根堆的新的堆顶，然后解锁A->B权值为3的路径，更新B的最短路径为5，执行结束

代码：

    //自定义节点的结构，一个节点包括的信息是当前节点合到初始节点的距离
    public static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    //自定义节点堆小根堆，小根堆上每个节点存储的是 当前结点和当前结点在数组中的下标
    public static class NodeHeap {
        //节点数组
        private Node[] nodes;
        //记录节点是否进入过堆，Node代表当前结点，Integer代表当前结点在堆上的位置
        private HashMap<Node, Integer> heapIndexMap;
        //node代表当前结点，Integer是当前结点到初始结点的距离
        private HashMap<Node, Integer> distanceMap;
        //节点堆的初始大小
        private int size;

        public NodeHeap(int size) {
            //这里的size是用户传来的整个图的节点的个数
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            this.size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void addOrUpdateOrIgnore(Node node, int distance) {
            //如果这个节点进入过堆并且没有弹出就更新他到原点的值
            if (inHeap(node)) {
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                //这里注意，insertHeapify的过程是把已经加入的节点和它以前在堆中的位置传进去进行生成小根堆的过程，所以之前的节点信息背覆盖了
                insertHeapify(node, heapIndexMap.get(node));
            }
            //如果这个节点没进入过，就直接分别在数组和堆里同步更新数据
            if (!isEntered(node)) {
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
        }

        public NodeRecord pop() {
            //把距离最小的元素取出来
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            //把头节点和最后一个位置的交换
            swap(0, size - 1);
            //说明当前结点已经弹出
            heapIndexMap.put(nodes[size - 1], -1);
            //移除
            distanceMap.remove(nodes[size - 1]);
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }

        //传进来的分别是节点，和节点当前的位置，但是建立是根据到原点的距离建立的
        private void insertHeapify(Node node, int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                        ? left + 1 : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        //堆和数组同步更新
        private void swap(int index1, int index2) {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    
    public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur, distance);
        }
        return result;
    }