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

algorithm java dijkstra

2022-09-01 18:08:58

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

答案 1

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

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

注意：

像任何优化一样，这个应该小心处理，并可能导致好奇和难以找到的错误（例如，请参阅此处）。在大多数情况下，只需使用 remove 和 re-insert 应该没问题，但是如果你的 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.

答案 2

您可以使用 TreeSet（C++，您可以使用 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）reduce键操作的优先级队列！
PriorityQueue在Java中确实存在，但该方法不是对数的，因此您的减少键操作将是O（n）而不是O（lgn），并且（渐近地）您将获得较慢的Dikjstra！remove(Object o)
要从无到有（使用for循环）构建TreeSet，需要时间O（nlgn），与从n个项目初始化堆/优先级队列的O（n）最坏情况时间相比，O（nlgn）要慢一些。然而，Dijkstra的主要循环需要时间O（nlgn + elgn），这主导了这个初始化时间。因此，对于Dijkstra来说，初始化TreeSet不会导致任何显着的减速。
我们不能使用 a，因为我们关心钥匙的顺序 - 我们希望能够首先拉出最小的钥匙。这为我们提供了具有最佳距离估计的节点！HashSet
TreeSet在Java中，它是使用红黑树实现的 - 一个自平衡的二叉搜索树。这就是为什么这些操作具有对数最坏情况时间的原因。
你使用 s 来表示图形节点，这很好，但是当你引入一个类时，你需要一种方法来关联这两个实体。我建议在构建图形时构建一个 - 这将有助于跟踪哪个对应于什么。`intNodeHashMap<Integer, Node>intNode