gpt4 book ai didi

c++ - 使用 STL make_heap 实现 Dijkstra 算法

转载 作者:行者123 更新时间:2023-11-30 00:58:22 29 4
gpt4 key购买 nike

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

Performance of Dijkstra's algorithm implementation

Implementing Dijkstra's Algorithm

鉴于 STL 不包含用于更新键的堆函数,在堆 (line 19) 中重新排序顶点的最佳方法是什么?

最佳答案

您需要让顶点在堆中“向上冒泡”(根据需要与父节点交换),直到它到达堆中的新位置。

在改编自《算法导论》第 2 版的伪 C++ 中。页。 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; }

关于c++ - 使用 STL make_heap 实现 Dijkstra 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6333847/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com