java 在 Dijkstra 算法中使用哪种数据类型作为队列？

Question

提问by D?nu

I'm trying to implement Dijkstra's algorithm in Java (self-study). I use the pseudo-code provided by Wikipedia (link). Now near the end of the algorithm, I should decrease-key v in Q;. I guess i should have implemented Q with a BinaryHeap or something like that? What would be the right (built-in) datatype to use here?

我正在尝试在 Java 中实现 Dijkstra 算法（自学）。我使用维基百科提供的伪代码（链接）。现在接近算法的结尾，我应该decrease-key v in Q;。我想我应该用 BinaryHeap 或类似的东西实现 Q ？在这里使用的正确（内置）数据类型是什么？

private void dijkstra(int source) {
        int[] dist = new int[this.adjacencyMatrix.length];
        int[] previous = new int[this.adjacencyMatrix.length];
        Queue<Integer> q = new LinkedList<Integer>();

        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            dist[i] = this.INFINITY;
            previous[i] = this.UNDEFINED;
            q.add(i);
        }

        dist[source] = 0;

        while(!q.isEmpty()) {
            // get node with smallest dist;
            int u = 0;
            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(dist[i] < dist[u])
                    u = i;
            }

            // break if dist == INFINITY
            if(dist[u] == this.INFINITY) break;

            // remove u from q
            q.remove(u);

            for(int i = 0; i < this.adjacencyMatrix.length; i++) {
                if(this.adjacencyMatrix[u][i] == 1) {
                    // in a unweighted graph, this.adjacencyMatrix[u][i] always == 1;
                    int alt = dist[u] + this.adjacencyMatrix[u][i]; 
                    if(alt < dist[i]) {
                        dist[i] = alt;
                        previous[i] = u;

                        // here's where I should "decrease the key"
                    }
                }
            }
        }
    }

Answer 1

回答by LiKao

The simplest way is to use a priority queue and not to care about the previously added key in the priority queue. This means you will have each node multiple times in the queue, but this does not hurt the algorithm at all. If you have a look at it, all versions of the node which have been replaced will be picked up later and by then the closest distance will already have been determined.

最简单的方法是使用优先队列，而不关心优先队列中先前添加的键。这意味着您将在队列中多次拥有每个节点，但这根本不会损害算法。如果你看一看，被替换的节点的所有版本都会稍后被拾取，到那时最近的距离已经确定了。

The check if alt < dist[v]:from the wikipedia is what makes this work. The runtime will only degrade a little from this, but if you need the very fast version you have to optimize further.

if alt < dist[v]:来自维基百科的检查是使这项工作的原因。运行时只会因此而降低一点，但是如果您需要非常快的版本，则必须进一步优化。

NOTE:

笔记：

Like any optimization, this one should be handled with care and may lead to curious and hard to find bugs (see e.g. here). For most cases, just using remove and re-insert should be fine, but the trick I mentioned here, can speed up your code a little if your Dijkstra implementation is the bottleneck.

像任何优化一样，应该小心处理这个优化，并且可能会导致好奇和难以发现的错误（参见例如这里）。在大多数情况下，只使用 remove 和 re-insert 应该没问题，但是如果您的 Dijkstra 实现是瓶颈，我在这里提到的技巧可以稍微加快您的代码速度。

Most importantly: Before trying this, make sure how your priority queue handles the priority. The actual priority in the queue should never change, or you may mess up invariants of the queue, which means items stored in the queue may not be retrievable any more. E.g. in Java, priorities are stored together with the object, so you do need an additional wrapper:

最重要的是：在尝试之前，请确保您的优先级队列如何处理优先级。队列中的实际优先级永远不应该改变，否则你可能会弄乱队列的不变量，这意味着存储在队列中的项目可能无法再检索了。例如，在 Java 中，优先级与对象存储在一起，因此您确实需要一个额外的包装器：

This will not work:

这将不起作用：

import java.util.PriorityQueue;

// Store node information and priority together
class Node implements Comparable<Node> {
  public int prio;
  public Node(int prio) { this.prio = prio; }

  public int compareTo(Node n) {
     return Integer.compare(this.prio, n.prio);
  }
}

...
...
PriorityQueue<Node> q = new PriorityQueue<Node>();
n = new Node(10);
q.add(n)
...
// let's update the priority
n.prio = 0;
// re-add
q.add(n);
// q may be broken now

Because at n.prio=0you are also changing the priority of the object within the queue. However, this will work fine:

因为n.prio=0你也在改变队列中对象的优先级。但是，这将正常工作：

import java.util.PriorityQueue;

// Only node information
class Node {
  // Whatever you need for your graph
  public Node() {}
}

class PrioNode {
   public Node n;
   public int prio;
   public PrioNode(Node n, int prio) {
     this.n = n;
     this.prio = prio;
   }

   public int compareTo(PrioNode p) {
      return Integer.compare(this.prio, p.prio);
   }
}

...
...
PriorityQueue<PrioNode> q = new PriorityQueue<PrioNode>();
n = new Node();
q.add(new PrioNode(n,10));
...
// let's update the priority and re-add
q.add(new PrioNode(n,0));
// Everything is fine, because we have not changed the value
// in the queue.

Answer 2

回答by James Lawson

You can use a TreeSet, (in C++ you can use a std::set) to implement your priority queue for Dijkstra. A TreeSetrepresents a set, but we also allowed to describe order of the items in the set. You need to store the nodes in the set and use the distances of the nodes to order the nodes. The node with smallest distance will be at the beginning of the set.

您可以使用 a TreeSet, （在 C++ 中您可以使用 a std::set）来实现 Dijkstra 的优先级队列。ATreeSet代表一个集合，但我们也允许描述集合中项目的顺序。您需要将节点存储在集合中，并使用节点的距离对节点进行排序。距离最小的节点将位于集合的开头。

class Node {
    public int id;   // store unique id to distinguish elements in the set
    public int dist; // store distance estimates in the Node itself
    public int compareTo(Node other) {
        // TreeSet implements the Comparable interface.
        // We need tell Java how to compare two Nodes in the TreeSet.
        // For Dijstra, we want the node with the _smallest_ distance
        // to be at the front of the set.
        // If two nodes have same distance, choose node with smaller id
        if (this.dist == other.dist) {
            return Integer.valueOf(this.id).compareTo(other.id);
        } else {
            return Integer.valueOf(this.dist).compareTo(other.dist);
        }
    }
}
// ...
TreeSet<Node> nodes = new TreeSet<Node>();

The extract-minoperation is implemented via the following and takes O(lgn) worst case time:

该提取物的最小操作经由以下实现，并且需要O（LGN）最坏情况时间：

Node u = nodes.pollFirst();

With the decrease-keyoperation, we remove the node with the old key (the old distance estimate) and add a new node with the smaller key (the new, better distance estimate). Both operations take O(lgn) worst case time.

通过减少键操作，我们删除具有旧键（旧距离估计）的节点并添加具有较小键（新的、更好的距离估计）的新节点。两种操作都需要 O(lgn) 最坏情况时间。

nodes.remove(v);
v.dist = /* some smaller key */
nodes.add(v);

Some extra notes:

一些额外的注意事项：

The above is very simple to implement and, because both of these operations are logarithmic in n, overall, the running time will be O((n + e)lgn). This is considered efficient for a basic implemtation of Dijkstra. See the CLRS book(ISBN: 978-0-262-03384-8) Chapter 19 for a proof of this complexity.
Although most textbooks will use a priority queue for Dijkstra, Prim, A*, etc., unfortunately neither Java nor C++ actually has a implementation of priority queue with the same O(lgn) decrease key operation!
PriorityQueuedoes exist in Java, but the remove(Object o)method is notlogarithmic and so your decrease-key operation would be O(n) instead of O(lgn) and (asymptotically) you'd get a slower Dikjstra!
To build up the TreeSet from nothing (using a for loop), it takes time O(nlgn) which is a bit slower compared to the O(n) worst case time to initialise a heap / priority queue from n items. However the main loop of Dijkstra takes time O(nlgn + elgn) which dominates this initialisation time. So for Dijkstra, initialising a TreeSet won't cause any significant slowdown.
We can't use a HashSetbecause we care about the order of the keys- we want to be able to pull out the smallest first. This gives us the node with the best distance estimate!
TreeSetin Java is implemented using a Red-Black tree - a self-balancing binary search tree. That's why these operations have logarithmicworst case time.
You're using ints to represent you graph nodes which is good but when you introduce a Nodeclass you'll need a way to relate the two entities. I'd recommending building a HashMap<Integer, Node>when you build you graph - it'll help keep track of which intcorresponds to what Node. `

上面实现起来非常简单，因为这两个操作都是n的对数，所以总体来说，运行时间将为O((n + e)lgn)。这对于 Dijkstra 的基本实现被认为是有效的。有关这种复杂性的证明，请参阅CLRS 书籍（ISBN：978-0-262-03384-8）第 19 章。
尽管大多数教科书都会使用优先级队列来表示 Dijkstra、Prim、A* 等，但不幸的是，Java 和 C++ 中实际上都没有实现具有相同 O(lgn) 减键操作的优先级队列！
PriorityQueueJava 中确实存在，但该remove(Object o)方法不是对数的，因此您的减键操作将是 O(n) 而不是 O(lgn) 并且（渐近）您会得到更慢的 Dikjstra！
要从无到有（使用 for 循环）构建 TreeSet，需要时间 O(nlgn)，与 O(n) 最坏情况时间相比，从 n 个项目初始化堆/优先级队列要慢一些。然而，Dijkstra 的主循环需要时间 O(nlgn + elgn)，它支配了这个初始化时间。因此，对于 Dijkstra，初始化 TreeSet 不会导致任何显着的减速。
我们不能使用 aHashSet因为我们关心键的顺序- 我们希望能够首先拉出最小的。这为我们提供了具有最佳距离估计的节点！
TreeSet在 Java 中使用红黑树实现 - 一种自平衡二叉搜索树。这就是这些操作具有对数最坏情况时间的原因。
您正在使用ints 来表示您的图形节点，这很好，但是当您引入一个Node类时，您将需要一种方法来关联两个实体。我建议HashMap<Integer, Node>在构建图形时构建一个- 它有助于跟踪哪个int对应于什么Node。`

Answer 3

回答by hammar

The suggested PriorityQueuedoes not provide a decrease-key operation. However, it can be emulated by removing the element and then reinserting it with the new key. ~~This should not increase the asymptotic run time of the algorithm, although it could be made slightly faster with built-in support.~~

建议PriorityQueue不提供减键操作。但是，可以通过删除元素然后使用新密钥重新插入来模拟它。~~这不应该增加算法的渐近运行时间，尽管它可以通过内置支持稍微快一点。~~

EDIT: This does increase the asymptotic run time, as decrease-key is expected to be O(log n)for a heap but remove(Object)is O(n). It appears there isn't any built-in priority queue in Java with support for an efficient decrease-key.

编辑：这确实增加了渐近运行时间，降低等键有望成为O(log n)一个堆，但remove(Object)为O(n)。Java 中似乎没有任何内置的优先级队列支持有效的减少键。

Answer 4

回答by zellio

Priority Queueas per the wiki article. Which suggests that the classic implementation now is to use a "min-priority queue implemented by a Fibonacci heap."

根据维基文章的优先级队列。这表明现在的经典实现是使用“由斐波那契堆实现的最小优先级队列”。

java 在 Dijkstra 算法中使用哪种数据类型作为队列？

提问by D?nu

回答by LiKao

回答by James Lawson

回答by hammar

回答by zellio

相关推荐

最近更新

标签

java 在 Dijkstra 算法中使用哪种数据类型作为队列？

提问by D?nu

回答by LiKao

回答by James Lawson

回答by hammar

回答by zellio

相关推荐

java WebView 不打开 android 默认视频播放器？

java 检查 Ant 脚本中是否设置了环境变量

java java中客户端和服务器之间的通信方式

java 属性文件的 MIME 类型是什么？

相关推荐

最近更新

标签