优先队列插入键值对

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）,因为每个边只更新一次距离。

“初始化堆需要线性时间，然后执行m次更新，每次更新的代价为O（log n)，总时间为O（mlog n）。”-http://www.cs.cmu.edu/~avrim/451f07/lectures/lect1011.pdf

这必须在一个具有特定名称的文件中完成（即，根据我的理解，我不能创建一个KeyValuePair类来实现Comparator)。

我很想听听你的想法。

Answer 1

我正在解决同样的问题。我知道你在哪里可以找到你问题的答案。这是一本很棒的书，有代码算法的例子，由罗伯特·塞奇威克和凯文·韦恩出版的第四版。

站点手册和代码示例（包括使用PriorityQueue实现Dijkstra算法）Dijkstra算法的这个实现不使用Java的标准PriorityQueue实现。相反，它实现了IndexMinPQ，这在本书的前面已经讨论过，并有详细的解释！