PriorityQueue+Dijkstra优先队列优化的Dijstra
前面分别介绍了“原生的Dijkstra”即毫无优化的Dijkstra,但这种Dijkstra的效率较低为n^n,因此面对较大数据量的时候需要对其进行优化,也就是优化所采用的贪心策略的实现,因此就有了Heao+Dijkstra堆优化的Dijkstra,但是堆优化的实现很复杂,而PriorityQueue+Dijkstra优先队列优化的Dijstra的效率虽然略低于堆优化的Dijkstra,但是实现却容易的多,也不容易出错,因为可以借助java类库中的PriorityQueue来实现,因此优先队列优化的Dijkstra是首选,其实java类库PriorityQueue的底层实现原理就是推排序。
还以蓝桥杯“最短路”为例实现PriorityQueue+Dijkstra:
给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。
第一行两个整数n, m。
接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。
1 2 -1
2 3 -1
3 1 2
-2
对于10%的数据,n = 2,m = 2。
对于30%的数据,n <= 5,m <= 10。
对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。
基于java类库的PriorityQueue的PriorityQueue+Dijkstra实现:
<span style="font-family:Microsoft YaHei;font-size:14px;"><span style="font-family:Microsoft YaHei;font-size:14px;">import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; import java.util.Set; /** * PriorityQueue + Dijkstra算法求单源最短路径 * 首推此方法 * 虽然优先级队列优化比堆优化性能差一点,差距很小。 * 但是优先级队列可以直接使用adt中的PriorityQueue来实现, * 而堆优化实现非常复杂。 * * @author DuXiangYu * */ public class DijKstra_link_Queue { static int nodeCount; static int edgeCount; // 邻接表表头数组 static Node[] firstArray; // 最短路径数组 // static int[] dist; // S集合,代表着已经找到最短路径的结点 static HashSet<Integer> s; // 映射集合 static dist[] distArray; // 优先级队列 static PriorityQueue<dist> pq; static int max = 1000000; /** * 结点类 * * @author DuXiangYu */ static class Node { // 邻接顶点map private HashMap<Integer, Integer> map = null; public void addEdge(int end, int edge) { if (this.map == null) { this.map = new HashMap<Integer, Integer>(); } this.map.put(end, edge); } } /** * dist: 保存源结点至每个结点的最短路径 * @author DuXiangYu * */ static class dist implements Comparable<dist> { int value; int index; public dist(int value, int index) { this.value = value; this.index = index; } @Override public int compareTo(dist o) { if (o.value < this.value) { return 1; } else if (o.value > this.value) { return -1; } else { return 0; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); nodeCount = sc.nextInt(); edgeCount = sc.nextInt(); firstArray = new Node[nodeCount + 1]; for (int i = 0; i < nodeCount + 1; i++) { firstArray[i] = new Node(); } for (int i = 0; i < edgeCount; i++) { int begin = sc.nextInt(); int end = sc.nextInt(); int edge = sc.nextInt(); firstArray[begin].addEdge(end, edge); } sc.close(); long begin = System.currentTimeMillis(); djst(); long end = System.currentTimeMillis(); System.out.println(end - begin + "ms"); } /** * Heap + Dijkstra算法实现 */ private static void djst() { s = new HashSet<Integer>(); pq = new PriorityQueue<dist>(nodeCount); distArray = new dist[nodeCount + 1]; Node tempNode = firstArray[1]; for (int i = 2; i < nodeCount + 1; i ++) { HashMap<Integer, Integer> tempMap = tempNode.map; if (tempMap.containsKey(i)) { dist d = new dist(tempMap.get(i), i); pq.offer(d); distArray[i] = d; } else { dist d = new dist(max, i); pq.offer(d); distArray[i] = d; } } s.add(1); while (s.size() < nodeCount) { dist d = pq.poll(); int index = d.index; int value = d.value; s.add(index); // 用indx这个点去更新它的邻接点到开始点的距离 HashMap<Integer, Integer> m = firstArray[index].map; if (m == null) { continue; } Set<Integer> set = m.keySet(); Iterator<Integer>it = set.iterator(); while (it.hasNext()) { int num = it.next(); if (num == 1) { continue; } dist tempDist = distArray[num]; if (m.get(num) + value < tempDist.value) { pq.remove(tempDist); tempDist.value = m.get(num) + value; pq.offer(tempDist); distArray[num] = tempDist; } } } for (int i = 2; i < nodeCount + 1; i ++) { System.out.println(distArray[i].value); } } }</span></span>
性能测试:
还是对于那个10000个结点和100000条边的测试数据来说,优先级队列优化的平均执行时间为320ms,看得出来比堆优化的执行效率略低,但相对原生的Dijkstra提升还是非常明显的:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。