dijkstra
前提：在一张图里，不能有权值为负数的边。
给你一个出发点，求出发点到所有结点的最短距离是多少？如果无法到达某个点，则到这个点的距离是正无穷（一般出现在有向图里面）。
举个，例子，看如下图：右边集合表示的是A点到集合中各个点的最短距离。
一开始，假设A点到所有其它点的距离是正无穷，就是假设都不可到达：
A作为一个桥连点出现后，A到B点的距离就是原先A到A（0）的距离加上A到B的距离（1），后面的类似，所以得到如下图：
当A这个点的记录使用完了之后，就永远不去改动它，就是上图中圈起来的A点。然后在剩下的记录中选一个最小的记录；B点对应1，意思就是从原点出发到达B的距离是1，再以B作为桥连点往外找。发现B到C的距离为2，B到E的距离为170，所以可以更新表中C点的记录为3（AB+BC），E的记录更新为171（AB+BE）。之后B点这条记录也永远不去改动。在表中使用了哪条记录就将其锁住，再也不碰它。
接下来，就是C点。。。同样的逻辑玩下去。最终表里全部锁死的记录就是dijkstra要求的记录。
注意，中间如果碰到距离相同的可以不更新。这好像有点贪心思想啊。
但问题是如何在表里找最小的记录呢，可以每次遍历来找，但是有点麻烦。所以更好的方式是利用小根堆。
小根堆会自动组织好，每次把最小的值弹出来，但在这里我们还有一个要求，就是我们有可能要更改已经在堆里组织好的值，这样的话，系统提供的堆实现不了。我们需要手动改写堆！推荐看看这两篇文章——系统提供的堆 VS 手动改写堆 & 堆排序，，。可以更好理解dijkstra算法的改进。
然后我们依次来看自己手写的小根堆要实现的功能有哪些，
1）add()，添加一条记录的方法，就是从原点到某个点的距离是多少，并且按距离来组织
2）update()，更新的方法，需要更新某条记录的距离。比如原点到X点的距离是100，但是通过某个桥连点到X的距离是20了，所以这条记录的距离就要更新成20，并且这条记录要在小根堆里往上heapInsert()，自动组织好顺序
3）ignore()，忽略点某个已经使用过的结点的方法。
小根堆里装的东西的结构就是：
public static class NodeRecord { public Node node; public int distance; public NodeRecord(Node node, int distance) { this.node = node; this.distance = distance; } }
以下代码分别实现了dijkstra算法的两种方法
package com.harrison.class11; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; import com.harrison.class11.Code01_NodeEdgeGraph.*; public class Code07_dijkstra { // 从from点到key的最短距离是value public static HashMap<Node, Integer> dijkstra1(Node from) { HashMap<Node, Integer> distanceMap = new HashMap<>(); distanceMap.put(from, 0);// 一开始，自己到自己的距离当然是0 // 锁住已经使用过的记录 HashSet<Node> selectedNodes = new HashSet<>(); Node minNode=getMinDistanceNodeAndUnselectedNode(distanceMap, selectedNodes); while(minNode!=null) { int distance=distanceMap.get(minNode); for(Edge edge:minNode.edges) { Node toNode=edge.to; if(!distanceMap.containsKey(toNode)) { distanceMap.put(toNode, distance+edge.weight); }else { distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance+edge.weight)); } } selectedNodes.add(minNode); minNode=getMinDistanceNodeAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } // 在distanceMap表里面排除掉在selectedNodes集合的点，然后选则距离最小的点返回 public static Node getMinDistanceNodeAndUnselectedNode( HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; // EntrySet可以遍历HashMap中的值 for(Entry<Node, Integer> entry:distanceMap.entrySet()) { Node node=entry.getKey(); int distance=entry.getValue(); if(!selectedNodes.contains(node) && distance<minDistance) { minNode=node; minDistance=distance; } } return minNode; } public static class NodeRecord{ public Node node; public int distance; public NodeRecord(Node n,int d) { node=n; distance=d; } } public static class NodeHeap{ // 实际的堆结构 private Node[] nodes; // key在堆中的位置就是value // 如果value是-1代表这个结点曾经进过堆（进来之后弹出了） private HashMap<Node, Integer> heapIndexMap; // 源结点到key的最小距离就是value private HashMap<Node, Integer> distanceMap; private int size;// 堆上有多少个点 public NodeHeap(int size) { nodes=new Node[size]; heapIndexMap=new HashMap<>(); distanceMap=new HashMap<>(); this.size=0; } public boolean isEmpty() { return size==0; } // 如果某个结点在heapIndexMap表有记录，表示曾经进过堆 public Boolean isEntered(Node node) { return heapIndexMap.containsKey(node); } public boolean inHeap(Node node) { return isEntered(node) && heapIndexMap.get(node)!=-1; } public void heapInsert(Node node,int index) { while(distanceMap.get(nodes[index])<distanceMap.get(nodes[(index-1)/2])) { swap(index, (index-1)/2); index=(index-1)/2; } } public void heapfiy(int index,int size) { int left=2*index+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=2*index+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; } // 有一个点node，如果发现了一个从源节点到node的距离为distance // 判断要不要更新，如果需要更新，就更新 public void addOrUpdateOrIgnore(Node node,int distance) { if(inHeap(node)) { // 如果结点在堆上，有可能更新完记录后，距离变小，所以需要调整堆 distanceMap.put(node, Math.min(distanceMap.get(node), distance)); heapInsert(node, heapIndexMap.get(node)); } if(!isEntered(node)){ // 如果没有进过堆，那么将这个结点挂在堆的最后一个结点 nodes[size]=node; // 这个结点的位置就在heapIndexMap表的size位置上 heapIndexMap.put(node, size); distanceMap.put(node, distance); heapInsert(node, size++); } // 如果两个if都没中，说明这个结点既不在堆上，但是又进来过， // 相当于什么都没做就直接返回 } public NodeRecord pop(){ NodeRecord nodeRecord=new NodeRecord(nodes[0], distanceMap.get(nodes[0])); swap(0, size-1); // 堆顶弹出后，标记为-1，并移除相应的距离记录 heapIndexMap.put(nodes[size-1], -1); distanceMap.remove(nodes[size-1]); // 释放size-1位置上的东西 nodes[size-1]=null; heapfiy(0, --size); return nodeRecord; } } // 改进后的dijkstra算法 // 从head出发，所有head能到达的结点 // 生成到达每个结点的最小路径记录并返回 public static HashMap<Node, Integer> dijkstra2(Node head,int size){ NodeHeap nodeHeap=new NodeHeap(size); nodeHeap.addOrUpdateOrIgnore(head, 0); HashMap<Node, Integer> ans=new HashMap<>(); while(!nodeHeap.isEmpty()) { NodeRecord recored=nodeHeap.pop(); Node cur=recored.node; int distance=recored.distance; for(Edge edge:cur.edges) { nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight+distance); } ans.put(cur, distance); } return ans; } }
