在Dijkstra算法中使用哪种数据类型作为队列？
我正在尝试用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 q = new LinkedList(); 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]:是否有效。 运行时只会稍微降低一点，但如果您需要非常快的版本，则必须进一步优化。
您可以使用TreeSet （在C ++中可以使用std::set ）来实现Dijkstra的优先级队列。 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 nodes = new TreeSet ();
extract-min操作通过以下方式实现，并采用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基本实现的有效方法。 有关此复杂性的certificate，请参阅CLRS书籍 （ ISBN：978-0-262-03384-8 ）第19章。
-
虽然大多数教科书都会使用Dijkstra，Prim，A *等优先级队列，但遗憾的是，Java和C ++实际上都没有优先级队列的实现，并且具有相同的O（lgn）减少键操作！
-
PriorityQueue确实存在于Java中，但remove(Object o)方法不是对数的，所以你的reduce-key操作将是O（n）而不是O（lgn）和（渐近地）你得到一个更慢的Dikjstra！ -
要从零开始构建TreeSet（使用for循环），与O（n）最坏情况时间相比，从n个项初始化堆/优先级队列需要时间O（nlgn）慢一点。 然而，Dijkstra的主循环需要时间O（nlgn + elgn），它占据了这个初始化时间。 因此对于Dijkstra来说，初始化TreeSet不会导致任何明显的减速。
-
我们不能使用
HashSet因为我们关心键的顺序 – 我们希望能够先取出最小的键 。 这为我们提供了最佳距离估计的节点！ -
Java中的
TreeSet是使用Red-Black树实现的 – 一种自我平衡的二叉搜索树。 这就是为什么这些操作具有对数最坏情况时间的原因。 -
您使用
int来表示图形节点，但是当您引入Node类时，您需要一种方法来关联这两个实体。 我建议在构建图形时构建HashMap– 它将帮助跟踪哪个int对应于哪个Node。 `
建议的PriorityQueue不提供减少键操作。 但是，可以通过删除元素然后使用新键重新插入它来模拟它。 这不应该增加算法的渐近运行时间，尽管可以通过内置支持稍微加快一点。
编辑 ：这确实增加了渐近运行时间，因为reduce-key预计为堆的O(log n) ，但remove(Object)是O(n) 。 看起来Java中没有任何内置优先级队列，支持有效的减少键。
根据维基文章的优先级队列 。 这表明现在的经典实现是使用“由Fibonacci堆实现的最小优先级队列”。