建个网站费用大概多少钱一年,做营销型网站哪家好,网站制作学什么,淘宝上可以做网站吗在上一篇迪瑞克斯拉算法中将功能实现了出来#xff0c;完成了图集中从源点出发获取所有可达的点的最短距离的收集。 但在代码中getMinDistanceAndUnSelectNode()方法的实现并不简洁#xff0c;每次获取minNode时#xff0c;都需要遍历整个Map#xff0c;时间复杂度太高。这…在上一篇迪瑞克斯拉算法中将功能实现了出来完成了图集中从源点出发获取所有可达的点的最短距离的收集。 但在代码中getMinDistanceAndUnSelectNode()方法的实现并不简洁每次获取minNode时都需要遍历整个Map时间复杂度太高。这篇文章主要是针对上一篇文章代码的一个优化。 其优化的过程中主要是用到了加强堆的数据结构如果不了解的强烈建议先看加强堆的具体实现。
回顾 上一篇中将确定不变的点放入Set中 每个点之间的距离关系放入Map中每次遍历Map获取最小minNode并根据该点找到所有的边算出最小距离后放入set中最终确定最小距离表。
优化 利用加强堆来维护点和距离的关系并利用小根堆的优势让最小的点总是在最上面需要注意的是以往的的加强堆中如果移除了这个元素会直接remove但是在这里不能remove因为要记录这个点是否在堆上是否加入过堆所以对于确定了的元素value要改成 -1用来标记当前元素已经确定不用再动。
加强堆代码 NodeHeap中的distanceMap用来表示点和距离的关系根据value的大小动态变化堆顶元素。 主方法是addOrUpdateOrIgnore()。 如果当前元素在堆中并且value ! 1inHeap说明元素还没有确定则判断进来的node和value是否大于当前堆中的node对应的value取小的更新如果更新还需要改变元素在堆中位置因为只可能越更新越小。所以要调用insertHeapify方法去改变堆结构。 如果元素还未加入过堆!isEntered则挂在堆尾并insertHeapify检查是否上移。 pop方法中如果弹出堆正常要删除但是不能删除除了和最后一个元素交换下移外将distanceMap中对应的值改为 -1。否则无法判断该元素是否已经加入过堆是否已经确定。
public static class NodeHeap {//Node类型的堆private Node[] nodes;//key对应的Node在堆中的位置是valueprivate HashMapNode, Integer heapIndexMap;//key对应的Node当前距离源点最近距离private HashMapNode, 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 this.size 0;}public boolean isEntered(Node head) {return heapIndexMap.containsKey(head);}public boolean inHeap(Node head) {return isEntered(head) heapIndexMap.get(head) ! -1;}public 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 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;}}public void insertHeapify(Node node, int index) {while (distanceMap.get(nodes[index]) distanceMap.get((index - 1) / 2)) {swap(distanceMap.get(nodes[index]), distanceMap.get((index - 1) / 2));index (index - 1) / 2;}}public NodeRecord pop() {NodeRecord nodeRecord new NodeRecord(nodes[0], distanceMap.get(0));swap(0, size - 1);heapIndexMap.put(nodes[size - 1], -1);distanceMap.remove(nodes[size - 1]);heapify(0, --size);return nodeRecord;}public void addOrUpdateOrIgnore(Node node, int distance) {if (inHeap(node)) {distanceMap.put(node, Math.min(distanceMap.get(node), distance));insertHeapify(node, distanceMap.get(node));}if (!isEntered(node)) {nodes[size] node;heapIndexMap.put(node, size);distanceMap.put(node, distance);insertHeapify(node, size);}}}主方法逻辑 上来将给定的点添加到堆中并且弹出遍历所有的边放到加强堆中去搞。 public static HashMapNode, Integer dijkstra2(Node head, int size) {NodeHeap nh new NodeHeap(size);nh.addOrUpdateOrIgnore(head, 0);HashMapNode, Integer result new HashMap();while (!nh.isEmpty()) {NodeRecord record nh.pop();Node cur record.node;int distance record.distance;for (Edge edge : cur.edges) {nh.addOrUpdateOrIgnore(edge.to, distance edge.weight);}result.put(cur, distance);}return result;}
