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

一尘不染

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

algorithm

我正在尝试在Java中实现Dijkstra的算法（自学）。我使用Wikipedia提供的伪代码（链接）。现在算法快要结束了，我应该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"
                    }
                }
            }
        }
    }

阅读 201

2020-07-28

共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.

2020-07-28