最短路问题

1.Dijkstra算法：可以获得以一个点为起点到所有其他点的最短路径的问题

* 思路：
* 从起点开始，遍历所有以起点为一端的所有边，通过这些边来更新其到其他点的距离，如果更新后更小则对该点最小
* 距离进行替换。一个点更新完后，去遍历整个点集，找到离起点距离最小的点，在重复以上步骤即可。

代码及解析：

 1 public static HashMap dijkstra(Node node) {
 2         HashMap disMap = new HashMap<>();//存放到每个点到起始点的最短距离
 3         HashSet set = new HashSet<>();//存放已经用来更新过的点
 4         disMap.put(node,0);//从起始点开始进行处理
 5         Node minNode = getMinNode(disMap,set);//初始化找到第一个点，后续开始进行循环操作
 6         while (minNode != null) {//只要能找到能更新的点就继续进行
 7             int distance = disMap.get(minNode);//最小点到起始点距离(后续这个点所带来的更新都要加该距离)
 8             for (Edge edge : minNode.edges) {//遍历最小点的所有的边
 9                 Node toNode = edge.to;
10                 if (!disMap.containsKey(toNode)) {//如果之前没有这个点的最短距离，就直接把这个距离存进去
11                     disMap.put(toNode, distance + edge.weight);
12                 }
13                 else {//如果比之前存的距离小,就进行替代更新
14                     disMap.put(toNode, Math.min(disMap.get(toNode), distance + edge.weight));
15                 }
16             }
17             set.add(minNode);//表示这条边已经更新过了，存到该集合进行记录
18             minNode = getMinNode(disMap,set);//继续找下一个没更新过的最小节点
19         }
20         return disMap;
21     }
22     
23     public static Node getMinNode(HashMap disMap,HashSet set) {//获取不在set中
24                                                                                    //距离最小的点
25         Node minNode = null;
26         int minDistance = Integer.MAX_VALUE;
27         for (Entry entry : disMap.entrySet()) {
28             if (!set.contains(entry.getKey()) && entry.getValue() < minDistance) {
29                 minDistance = entry.getValue();
30                 minNode = entry.getKey();
31             }
32         }
33         return minNode;
34     }

2.Dijkstra算法的优化：小根堆的方式进行优化

优化思路：
因为dijkstra算法每次都是获取距离最小的那个点，所以可以将所有点到起始点的距离用一个小根堆来进行维护，每次便可以快速的取出最小距离进行处理。

算法实现的代码：

 1 public static HashMap dijkstra(Node node,int size) {
 2         NodeHeap nodeHeap = new NodeHeap(size);
 3         nodeHeap.addOrUpdateOrIgnore(node, 0);
 4         HashMap disMap = new HashMap<>();
 5         while (!nodeHeap.isEmpty()) {
 6             NodeRecord nodeRecord = nodeHeap.pop();
 7             disMap.put(nodeRecord.node, nodeRecord.distance);
 8             for (Edge edge : nodeRecord.node.edges) {
 9                 nodeHeap.addOrUpdateOrIgnore(edge.to, nodeRecord.distance + edge.weight);
10             }
11         }
12         return disMap;
13     }

小根堆的维护：

 1 public static class NodeRecord{//设立一个专门求最短路的点类，存点和该点到起始点的距离
 2         Node node;
 3         int distance;
 4         
 5         public NodeRecord(Node node,int distance) {
 6             this.node = node;
 7             this.distance = distance;
 8         }
 9     }
10     
11     public static class NodeHeap {//点的小根堆
12         private Node[] nodes;//点集数组用于存放所有的点
13         private HashMap heapIndexMap;//记录每个点所在的下标
14         private HashMap distanceMap;//记录每个点距离起始点的距离
15         private int size;//当前已插入的点的个数
16         
17         public NodeHeap(int size) {
18             nodes = new Node[size];
19             heapIndexMap = new HashMap<>();
20             distanceMap = new HashMap<>();
21             this.size = 0;
22         }
23         
24         public boolean isEmpty() {
25             return size == 0;
26         }
27         
28         public boolean isEntered(Node node) {//判断这个点是否插入过堆中
29             return heapIndexMap.containsKey(node);
30         }
31         
32         public boolean inHeap(Node node) {//判断这个点是否还在堆中
33             //如果已经加入过，并且这个点还没有被弹出来则在堆中
34             return isEntered(node) && heapIndexMap.get(node) != -1;
35         }
36         
37         public NodeRecord pop() {//弹出堆顶的元素
38             NodeRecord nodeRecord = new NodeRecord(nodes[0],distanceMap.get(nodes));//获得要弹出的点
39             //弹出堆顶元素后，要对整个堆进行调整，使其保持小根堆形态
40             swap(0,size - 1);//将这个已被拿出的点移到点集数组的最后
41             heapIndexMap.put(nodes[size - 1], -1);//将其下标置为-1(-1表示该点已从堆中弹出)
42             distanceMap.remove(nodes[size - 1]);//移出距离的哈希表
43             nodes[size - 1] = null;//将该点置为空，进行移除操作
44             heapify(nodes[0],--size);//进行小根堆的调整，并将size减1
45             return nodeRecord;
46         }
47         
48         //根据该点的情况，对小根堆进行增添/更新/不做任何操作
49         public void addOrUpdateOrIgnore(Node node,int distance) {
50             if (inHeap(node)) {//如果该点在堆中，则进行更新操作
51                 distanceMap.put(node,Math.min(distanceMap.get(node), distance));
52                 heapInsert(node,heapIndexMap.get(node));
53             }
54             if (!isEntered(node)) {//如果不在堆中，则进行增添操作
55                 nodes[size] = node;
56                 heapIndexMap.put(node, size);
57                 distanceMap.put(node,distance);
58                 heapInsert(node,size++);
59             }
60         }
61         
62         public void heapInsert(Node node,int index) {//小值向上调整
63             while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
64                 swap(index,(index - 1) / 2);
65                 index = (index - 1) / 2;
66             }
67         }
68         
69         public void heapify(Node node,int index) {//大值向下调整 
70             int left = 2 * index + 1;
71             while (left < size) {
72                 int smallest = left;
73                 if (left + 1 < size) {
74                     smallest = distanceMap.get(nodes[left]) < distanceMap.get(nodes[left + 1]) ? left :
75                                 left + 1;
76                 }
77                 if (distanceMap.get(nodes[smallest]) >= distanceMap.get(index)) {
78                     smallest = index;
79                 }
80                 if (smallest == index) {
81                     break;
82                 }
83                 swap(smallest,index);
84                 index = smallest;
85                 left = 2 * index + 1;
86             }
87         }
88         
89         private void swap(int index1,int index2) {
90             heapIndexMap.put(nodes[index1],    index2);
91             heapIndexMap.put(nodes[index2], index1);
92             Node tmp1 = nodes[index1];
93             nodes[index1] = nodes[index2];
94             nodes[index2] = tmp1;
95         }
96     }