求教如何用Java里的PriorityQueue来运用Dij算法

Dij求最短路径并不难理解，但是不知道怎么运用priorityqueue来写，主要是changepriority这个方法是没有的，网上找了很多现成代码，很少用priorityqueue直接解决

伪代码如下

forall u∈V:

dist[u] ← ∞,

prev[u] ← nil

dist[S] ← 0

H ← MakeQueue(V ) {dist-values askeys}while H is not empty:

u ← ExtractMin(H)for all (u,v)∈E:

if dist[v]>dist[u]+w(u,v):

dist[v] ←dist[u] + w(u, v)

prev[v] ← u

ChangePriority(H, v , dist [v ])

1.   private static int distance(ArrayList<Integer>[] adj, ArrayList<Edge>[] adjEdge, int s, int t) {
   
2.         int[] dist = new int[adj.length];
   
3.         for (int i = 0; i < adj.length; i++) {
   
4.                 dist[i] = Integer.MAX_VALUE;
   
5.         }
   
6.         dist[s] = 0;
   
7.         PriorityQueue<Node> pq = new PriorityQueue<Node>(adj.length, new Node());
   
8.         pq.add(new Node(s,0));
   
9.         while (!pq.isEmpty()) {
   
10.                 int u = pq.remove().vertex;
    
11.                 for (Edge e: adjEdge[u]) {
    
12.                         int w = e.to;
    
13.                         if (dist[w] > dist[u] + e.weight) {
    
14.                                 [b]if (pq.contains(Node(w, dist[w]))) [/b]{ // 这两行代码不知道怎么解决
    
15.                                         [b]pq.remove(Node(w, dist[w]));[/b]
    
16.                                 }
    
17.                                 dist[w] = dist[u] + e.weight;
    
18.                                 pq.add(new Node(w, dist[w]));
    
19.                         }
    
20.                 }
    
21.         }
    
22.         return dist[t];        
    
23. 
    
24.     }
    
25. 
    
26.         static class Node implements Comparator<Node> {
    
27.             public int vertex;
    
28.             public int cost;
    
29.    
    
30.             public Node() {
    
31.                    
    
32.             }
    
33.             public Node(int v, int cost) {
    
34.                     this.vertex = v;
    
35.                     this.cost = cost;
    
36.               }
    
37.   
    
38.             public int compare(Node n1, Node n2) {
    
39.                     if (n1.cost < n2.cost) return -1;
    
40.                 else if (n1.cost > n2.cost) return 1;
    
41.                 return 0;
    
42.              }
    
43.     }
    
44.    

复制代码

desperatelife 发表于 2016-8-5 18:11

你的代码做不到O（nlogn）的 直接remove的 时间复杂度是O（n）。我想过一种方法，就是什么都不更改直接insert进去，反正最小的一定是在最顶 然后一个HashSet记录访问过的节点 访问过的扔掉就可以了

java 内置的 heap 据我所知不支持高效的 decrease-key 或者 remove - update priority 操作。。但 heap 类结构里面对 decrease-key 操作比较友好的有 fibonacci heap，均摊复杂度可以达到 Theta(1)，但是常数项比较高，只在做 dijkstra 或者 minimum spanning tree 的时候效果还不错，然而操作繁琐，写起来也很爆炸。。。

只是面试的话，个人觉得用 priority queue 内置的 remove 就好了，可以和面试官提一下用 hash heap 优化 remove / update 的时间复杂度。以上两种 heap 在面试时间内写完并且解释清楚，都不容易。

1. template<typename T, typename Priority_T>
   
2. struct PriorityQueue {
   
3.   typedef pair<Priority_T, T> Element;
   
4.   priority_queue<Element, vector<Element>,
   
5.                  std::greater<Element>> elements;
   
6. 
   
7.   inline bool empty() const { return elements.empty(); }
   
8. 
   
9.   inline void put(T item, Priority_T priority) {
   
10.     elements.emplace(priority, item);
    
11.   }
    
12. 
    
13.   inline T get() {
    
14.     T minP = elements.top().second;
    
15.     elements.pop();
    
16.     return minP;
    
17.   }
    
18. };

复制代码