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

Question

我正在尝试用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

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

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

注意:

像任何优化一样,这个应该小心处理,并可能导致好奇和难以找到错误(参见例如这里).对于大多数情况,只使用删除和重新插入应该没问题,但是我在这里提到的技巧可以加快你的代码,如果你的Dijkstra实现是瓶颈.

最重要的是:在尝试此操作之前,请确保优先级队列如何处理优先级.队列中的实际优先级永远不会改变,或者您可能弄乱队列的不变量,这意味着存储在队列中的项目可能不再可检索.例如,在Java中,优先级与对象一起存储,因此您需要一个额外的包装器:

这不起作用:

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

因为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

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

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>();

该提取物的最小操作经由以下和需要O(LGN)实施最坏情况时间:

Node u = nodes.pollFirst();

使用减小键操作,我们使用旧密钥(旧距离估计)移除节点,并添加具有较小密钥的新节点(新的,更好的距离估计).两个操作都采用O(lgn)最坏情况时间.

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

一些额外的说明:

• 上面的实现非常简单,因为这两个操作都是n的对数,总的来说,运行时间将是O((n + e)lgn).这被认为是Dijkstra基本实现的有效方法.有关此复杂性的证明,请参阅CLRS书籍(ISBN:978-0-262-03384-8)第19章.

• 虽然大多数教科书都会使用Dijkstra,Prim,A*等优先级队列,但遗憾的是Java和C++实际上都没有优先级队列的实现,并且具有相同的O(lgn)减少键操作!

• PriorityQueue确实存在于Java中,但该remove(Object o)方法不是对数的,所以你的减少键操作将是O(n)而不是O(lgn)和(渐近地)你得到一个更慢的Dikjstra!

• 要从零构建TreeSet(使用for循环),与O(n)最坏情况时间相比,从n个项初始化堆/优先级队列需要时间O(nlgn).然而,Dijkstra的主循环需要时间O(nlgn + elgn),它占据了这个初始化时间.所以对于Dijkstra来说,初始化TreeSet不会导致任何明显的减速.

• 我们不能使用a,HashSet因为我们关心键的顺序 - 我们希望能够首先拉出最小的键.这为我们提供了最佳距离估计的节点!

• TreeSetJava中使用Red-Black树实现 - 一种自平衡二进制搜索树.这就是为什么这些操作具有对数最坏情况时间的原因.

• 您使用ints来表示图形节点,但是当您引入Node类时,您需要一种方法来关联这两个实体.我建议HashMap<Integer, Node>在构建图形时构建一个- 它将帮助跟踪哪些int对应于什么Node.`