实施Dijkstra算法使用STL make_heap

Question

至少几个答案建议使用STL堆函数来实现Dijkstra算法优先级队列：

Performance of Dijkstra's algorithm implementation

Implementing Dijkstra's Algorithm

什么是重新排序的最佳方式堆中的顶点（line 19），因为STL不包含用于更新密钥的堆函数？

Answer 1

您需要让顶点'通过堆向上冒泡'（根据需要将其与父级交换），直到它到达堆中的新位置。

在伪C++改编自Introduction to Algorithms 2nd ed。皮克。 140：

heap[pos] = new_weight; 
while (pos > 0 && heap[parent(pos)] > heap[pos]) { 
    swap(heap[parent(pos)], heap[pos]); 
    pos = parent(pos); 
} 

其中int parent(int pos) { return (pos-1)/2; }

Answer 2

我想有几个方法可以做到这一点。

您可以手动执行筛选操作，并将该值基本上携带到堆顶部，然后弹出，然后用堆叠的新值将其推回到堆上。

您可以更新该值并在堆上再次执行make_heap，假设make_heap在堆已经“几乎堆”时设计为高效。

您可以用一些标记来标记堆中的节点，以指示它不再有效，然后使用堆中的新值推送新元素。然后，每次从堆中弹出一个元素时，都会检查该标志的有效性并忽略任何无效元素。

否则，您可以使用另一个具有更新功能的堆实现。例如，Boost.Graph库在其详细信息（boost/graph/detail文件夹）中包含一个d_ary_heap.hpp头，该头实现了具有更新函数logN的D-Ary Heap间接实现。这用于Dijkstra和A *的BGL实现，您可以直接使用它，而不是实现自己的实现。