使用STL make_heap来实现Dijkstra的算法

|| 至少有两个答案建议使用STL堆函数在Dijkstra的算法中实现优先级队列： Dijkstra算法实现的性能实现Dijkstra算法鉴于STL不包含用于更新键的堆函数，什么是在堆中重新排列顶点的最佳方法（第19行）？

已邀请:

2 个回复

您需要让顶点在整个堆中“冒泡”（根据需要将其与父对象交换），直到到达顶点在堆中的新位置为止。在伪c ++中改编自算法概论第二版。 pg。 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; }

掸牛浓疗

我猜有几种方法可以做到。您可以手动进行筛选操作，基本上将值携带到堆的顶部，将其弹出，然后将其以新值推回堆中。您可以更新值并在堆上再次执行make_heap，前提是make_heap设计为在堆已经“几乎是堆”时有效。您可以用一些标志标记堆中的节点以表明它不再有效，然后将具有新值的新元素压入堆。然后，每次从堆中弹出一个元素时，都要检查标志的有效性，并忽略任何无效的元素。否则，您可以使用另一个具有更新功能的堆实现。例如，Boost.Graph库在其详细信息（boost / graph / detail文件夹）中包含d_ary_heap.hpp标头，该标头实现了D-Ary Heap间接实现，该实现确实具有logN的更新功能。这在Dijkstra和A *的BGL实现中使用，您也可以直接使用它们，而不用自己实现。

要回复问题请先登录或注册

使用STL make_heap来实现Dijkstra的算法

2 个回复

发起人

stl

implementation

dijkstra

c++

问题状态

使用STL make_heap来实现Dijkstra的算法

与内容相关的链接

2 个回复

发起人

stl

implementation

dijkstra

c++

问题状态