java - 优先级队列插入键值对java

Question

背景

我正在尝试在 O(mlogn) 时间内编写 Dijkstra 算法，其中 m 是边数，n 是节点数。我用来查找给定起始节点和给定结束节点之间的最短路径。我对此还很陌生。

这是我提出的算法:

假设图由邻接矩阵表示，每个节点都有一个行索引。

Initialize starting node distance to zero, and all other nodes to inifinity, in the heap.

Create a list of shortest paths, equal to the number of nodes in the graph, set to 0.

While the index of the node that corresponds to the minimum element in the heap 
has no value in the list of shortest paths and heap has node distances, do:
    Remove the minimum node distance from the heap, and bubble as necessary to fill the removed node.
    Put the minimum node distance into the list of shortest paths at its row index.

    For all nodes that were adjacent to the node with the minimum distance (that was just removed), do:
      Update the distances in the heap for the current node, using the following calculation:
        min((deleted node distance + adjacent edge weight), current node's distance)
    Reorganize the heap to be a minimum heap.

Return value in the list of shortest paths at the location of the end node.

这是 O(mlogn)，因为每个边只更新一次距离。

"It takes linear time to initialize the heap, and then we perform m updates at a cost of O(log n) each for a total time of O(mlog n)." - http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

问题

为了更新堆中正确位置的起始顶点的距离，向堆的插入必须是键值对 - 键是节点(行索引)，值是距离。

有讲座幻灯片online也就是说，优先级队列 ADT 中的每个条目都是一个键值对(否则，它如何确定优先级？)。

问题

PriorityQueue 的方法最多有一个参数，那么如何插入与值关联的键呢？

这必须在具有特定名称的单个文件中完成(即，据我所知，我无法创建一个实现 Comparator 的 KeyValuePair 类)。

我很想听听你的想法。

Answer 1

要为您的应用程序使用 JDK 的优先级队列实现，您可以维护 Map<Key, Value>除了 PriorityQueue<Value> 。在你的情况下，Key代表一个节点，Value是与节点保持最短距离的对象。要更新到节点的距离，首先在 map 中查找其相应的距离对象。然后，从优先级队列中删除距离对象。接下来，更新距离对象。最后，将距离对象插回到优先级队列中。