我正在尝试在 Java 中实现 Dijkstra 的算法(自学)。我使用维基百科提供的伪代码 (link)。现在接近算法的结尾，我应该减少Q中的key v;。我想我应该用 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"
                    }
                }
            }
        }
    }

最佳答案

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

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

注意:

像任何优化一样，这个优化应该小心处理，可能会导致好奇和难以发现的错误(参见例如 here)。在大多数情况下，仅使用 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.

关于java - 在 Dijkstra 算法中使用哪种数据类型作为队列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6267172/