一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 480|回复: 4
收起左侧

[树/链表/图] 求教如何用Java里的PriorityQueue来运用Dij算法

[复制链接] |试试Instant~ |关注本帖
desperatelife 发表于 2016-8-5 17:59:53 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 desperatelife 于 2016-8-5 18:01 编辑

Dij求最短路径并不难理解,但是不知道怎么运用priorityqueue来写,主要是changepriority这个方法是没有的,网上找了很多现成代码,很少用priorityqueue直接解决
伪代码如下
forall u∈V:
dist ← ∞,
prev ← 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+w(u,v):
dist[v] ←dist + w(u, v)
prev[v] ← u
ChangePriority(H, v , dist [v ])


 楼主| desperatelife 发表于 2016-8-5 18:11:07 | 显示全部楼层
  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.         static class Node implements Comparator<Node> {
  25.             public int vertex;
  26.             public int cost;
  27.    
  28.             public Node() {
  29.                    
  30.             }
  31.             public Node(int v, int cost) {
  32.                     this.vertex = v;
  33.                     this.cost = cost;
  34.               }
  35.   
  36.             public int compare(Node n1, Node n2) {
  37.                     if (n1.cost < n2.cost) return -1;
  38.                 else if (n1.cost > n2.cost) return 1;
  39.                 return 0;
  40.              }
  41.     }
  42.    
复制代码
回复 支持 反对

使用道具 举报

runrain 发表于 2016-8-15 21:20:28 | 显示全部楼层

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

使用道具 举报

mnmunknown 发表于 2016-8-15 22:16:20 | 显示全部楼层
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 在面试时间内写完并且解释清楚,都不容易。
回复 支持 反对

使用道具 举报

ArthurChen 发表于 2016-8-19 02:22:18 | 显示全部楼层
  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.   inline bool empty() const { return elements.empty(); }

  7.   inline void put(T item, Priority_T priority) {
  8.     elements.emplace(priority, item);
  9.   }

  10.   inline T get() {
  11.     T minP = elements.top().second;
  12.     elements.pop();
  13.     return minP;
  14.   }
  15. };
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 20:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表