heap - 如何在Dijkstra算法中使用二进制堆？

Question

我正在编写dijkstra算法的代码，对于我们应该找到距当前正在使用的节点最小距离的节点的部分，我正在使用一个数组，并将其完全遍历以找出该节点。

这部分可以用二进制堆代替，我们可以在O(1)时间内找出节点，但是我们还会在进一步的迭代中更新节点的距离，我将如何合并该堆？

如果是数组，我要做的就是转到(ith -1)索引并更新该节点的值，但是在Binary堆中无法完成相同的事情，我将必须进行完整的搜索才能得出图确定节点的位置，然后对其进行更新。

解决此问题的方法是什么？

Answer 1

这只是我在类里面与同学分享的一些信息。我以为我可以使人们更容易找到它，所以我把这篇文章留了下来，以便我找到解决方案时可以回答。

注意:在此示例中，我假设您图形的顶点具有一个ID来跟踪哪个是哪个。可以是名称，数字或其他名称，只要确保您在下面的struct中更改类型即可。
如果没有这种区分方法，则可以使用指向顶点的指针并比较其指向的地址。

您在这里面临的问题是，在Dijkstra的算法中，要求我们将图的顶点及其键存储在此优先级队列中，然后更新队列中剩余的键。
但是...堆数据结构无法到达不是最小或最后一个节点的任何特定节点!
我们能做的最好的事情是在O(n)时间内遍历堆以找到它，然后在O(Logn)处更新其密钥和冒泡。这使得为​​每个边更新所有顶点O(n)，使得我们实现Dijkstra O(mn)的方式比最优O(mLogn)差。

!一定有更好的方法!

因此，我们需要实现的并不是完全基于标准的基于最小堆的优先级队列。我们需要比标准的4 pq操作多一个操作:

IsEmpty

添加

PopMin

PeekMin

和DecreaseKey

为了DecreaseKey，我们需要:

在堆

中找到特定的顶点

降低其键值

“堆”或“冒泡”顶点

本质上，由于您(我假设它已在过去4个月的某个时间实现)可能会使用“基于数组”的堆实现，
这意味着我们需要堆来跟踪数组中每个顶点及其索引，以便使此操作成为可能。

像这样设计一个 struct(C++)

struct VertLocInHeap
{
    int vertex_id;
    int index_in_heap;
};

可以让您对其进行跟踪，但是将它们存储在数组中仍然会给您O(n)时间来查找堆中的顶点。没有改善复杂性，并且比以前更复杂。 >。<
我的建议(如果目标是优化):

将此信息存储在二进制值为“vertex_id”

的二进制搜索树中

进行二进制搜索以找到顶点在O(Logn)堆中的位置

使用索引访问顶点并更新其在O(1)中的键

使O(Logn)中的顶点冒泡

我实际上使用了一个 std::map 声明为:
std::map m_locations;
在堆中而不是使用struct。第一个参数(键)是vertex_id，第二个参数(值)是堆数组中的索引。
由于 std::map保证O(Logn)搜索，因此开箱即用的效果很好。然后每当您插入或冒泡时，您只需 m_locations[vertexID] = newLocationInHeap;快钱。

分析:
上行:现在我们有了O(Logn)，可以在p-q中查找任何给定的顶点。对于冒泡，我们进行O(Log(n))移动，对于每次交换，在数组索引映射中执行O(Log(n))搜索，从而产生冒泡的O(Log ^ 2(n)操作-向上。
因此，我们有一个Log(n)+ Log ^ 2(n)= O(Log ^ 2(n))操作，用于为单个边缘更新堆中的键值。这使我们的Dijkstra alg取O(mLog ^ 2(n))。这非常接近理论上的最佳值，至少与我所能达到的最接近。真棒负鼠!
缺点:我们实际上在堆中存储的信息量是内存的两倍。这是“现代”问题吗？并不是的;我的桌面可以存储超过80亿个整数，许多现代计算机都配备了至少8GB的RAM。但是，这仍然是一个因素。如果您用40亿个顶点的图形进行此实现，并且发生的次数比您想象的要多得多，那么它将引起问题。同样，所有这些可能不会影响分析复杂性的额外读/写操作在某些机器上仍会花费一些时间，尤其是在信息存储在外部的情况下。

我希望这对以后的人有所帮助，因为我有一段时间发现所有这些信息，然后将我从这里，那里和各处得到的碎片拼凑在一起，形成了一个恶魔。我指责互联网和睡眠不足。