如何在Dijkstra算法中使用二进制堆？ [英] How can I use binary heap in the Dijkstra algorithm?

问题描述

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

这部分可以用二进制堆代替，我们可以在O（1）时间内计算出节点，但是我们还会在进一步的迭代中更新节点的距离，我会合并该堆吗？

对于数组，我要做的就是转到（ith -1）索引并更新该节点的值，但是在Binary堆中无法完成相同的操作，我将必须进行完整搜索以找出节点的位置，然后对其进行更新。

什么是解决方法

解决方案

这只是我在课堂上与同班同学分享的一些信息。我以为我会让人们更容易找到它，所以我把这篇帖子留了下来，以便我找到解决办法时可以回答。

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

您遇到的问题面临的一个事实是，在Dijkstra的算法中，要求我们将图的顶点及其键存储在此优先级队列中，然后更新队列中剩下的键。
但是... 堆数据结构无法到达不是最小或最后一个节点的任何特定节点！

我们最好的能够做到的是在O（n）时间内遍历堆以找到它，然后在O（Logn）处更新其键并进行冒泡。这使得更新每个顶点的所有顶点 O（n），使我们实现Dijkstra O（mn）的效果远不及最优O（mLogn）。

B！必须有更好的方法！

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

1. IsEmpty


2. 添加


3. PopMin


4. PeekMin


5. 和 DecreaseKey

要 DecreaseKey ，我们需要：

• 在堆中找到特定的顶点


• 降低键值


• 堆积或冒泡该顶点

从本质上讲，由于您（我假设它已在过去4个月的某个时间实施），可能要使用数组基于的堆实现，
表示我们需要堆来跟踪数组中每个顶点及其索引，以便可以执行此操作。

设计结构如：（c ++）

  struct VertLocInHeap 
 {
 int vertex_id; 
 int index_in_heap; 
}; 
  

将允许您跟踪它，但是将它们存储在数组中仍然会给您O（ n）在堆中查找顶点的时间。没有改善复杂性，并且比以前更加复杂。 >。<

我的建议（如果这里是优化的目标）：

1. 将此信息存储在关键值为`vertex_id`的二叉搜索树中。
   
2. 进行二叉搜索以找到顶点在O（Logn）中堆中的位置


3. 使用索引访问顶点并更新其在O（1）中的键


4. 在O（Logn）中填充顶点
>

我实际上使用了 / code> std :: map 声明为：
std :: map m_locations;
在堆中而不是使用struct。第一个参数（键）是vertex_id，第二个参数（值）是堆数组中的索引。
因为 std :: map 可以保证O（Logn）搜索，所以开箱即用的效果很好。然后，无论何时插入或冒泡，您只需 m_locations [vertexID] = newLocationInHeap;

轻松赚钱。

分析：

上方：现在，我们有O（Logn）可以在pq。对于冒泡，我们进行O（Log（n））移动，对于每次交换，在数组索引映射中进行O（Log（n））搜索，从而产生冒泡的O（Log ^ 2（n）操作-up。

因此，我们有一个Log（n）+ Log ^ 2（n）= O（Log ^ 2（n））操作来更新其中的键值
缺点：我们实际上在堆中存储的信息是存储在堆中的信息的两倍，这是一个现代问题吗？至少要有8GB的RAM；但是，这仍然是一个因素。如果您以40亿个顶点的图形来执行此实现，并且发生的次数比您想像的要多得多，那么它就会引起问题。这些可能不会影响分析复杂性的额外读/写操作在某些计算机上可能仍会花费一些时间，尤其是在

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

I am writing code of dijkstra algorithm, for the part where we are supposed to find the node with minimum distance from the currently being used node, I am using a array over there and traversing it fully to figure out the node.

This part can be replaced by binary heap and we can figure out the node in O(1) time, but We also update the distance of the node in further iterations, How will I incorporate that heap?

In case of array, all I have to do is go to the (ith -1) index and update the value of that node, but same thing can't be done in Binary heap, I will have to do the full search to figure out the position of the node and then update it.

What is workaround of this problem?

解决方案

This is just some information I found while doing this in a class, that I shared with my classmates. I thought I'd make it easier for folks to find it, and I had left this post up so that I could answer it when I found a solution.

Note: I'm assuming for this example that your graph's vertices have an ID to keep track of which is which. This could be a name, a number, whatever, just make sure you change the type in the struct below. If you have no such means of distinction, then you can use pointers to the vertices and compare their pointed-to addresses.

The problem you are faced with here is the fact that, in Dijkstra's algorithm, we are asked to store the graphs vertices and their keys in this priority queue, then update the keys of the ones left in the queue. But... Heap data-structures have no way of getting at any particular node that is not the minimum or the last node!
The best we'd be able to do is traverse the heap in O(n) time to find it, then update its key and bubble-it-up, at O(Logn). That makes updating all vertices O(n) for every single edge, making our implementation of Dijkstra O(mn), way worse than the optimal O(mLogn).

Bleh! There has to be a better way!

So, what we need to implement isn't exactly a standard min-heap-based priority queue. We need one more operation than the standard 4 pq operations:

1. IsEmpty
2. Add
3. PopMin
4. PeekMin
5. and DecreaseKey

In order to DecreaseKey, we need to:

• find a particular vertex inside the Heap
• lower its key-value
• "heap-up" or "bubble-up" the vertex

Essentially, since you were (I'm assuming it has been implemented sometime in the past 4 months) probably going to use an "array-based" heap implementation, this means that we need the heap to keep track of each vertex and its index in the array in order for this operation to be possible.

Devising a struct like: (c++)

struct VertLocInHeap
{
    int vertex_id;
    int index_in_heap;
};

would allow you to keep track of it, but storing those in an array would still give you O(n) time for finding the vertex in the heap. No complexity improvement, and it's more complicated than before. >.<
My suggestion (if optimization is the goal here):

1. Store this info in a Binary Search Tree whose key value is the `vertex_id`
2. do a binary-search to find the vertex's location in the Heap in O(Logn)
3. use the index to access the vertex and update its key in O(1)
4. bubble-up the vertex in O(Logn)

I actually used a std::map declared as: std::map m_locations; in the heap instead of using the struct. The first parameter (Key) is the vertex_id, and the second parameter (Value) is the index in the heap's array. Since std::map guarantees O(Logn) searches, this works nicely out-of-the-box. Then whenever you insert or bubble, you just m_locations[vertexID] = newLocationInHeap;
Easy money.

Analysis:
Upside: we now have O(Logn) for finding any given vertex in the p-q. For the bubble-up we do O(Log(n)) movements, for each swap doing a O(Log(n)) search in the map of array indexes, resulting in a O(Log^2(n) operation for bubble-up.
So, we have a Log(n) + Log^2(n) = O(Log^2(n)) operation for updating the key values in the Heap for a single edge. That makes our Dijkstra alg take O(mLog^2(n)). That's pretty close to the theoretical optimum, at least as close as I can get it. Awesome Possum!
Downside: We are storing literally twice as much information in-memory for the heap. Is it a "modern" problem? Not really; my desky can store over 8 billion integers, and many modern computers come with at least 8GB of RAM; however, it is still a factor. If you did this implementation with a graph of 4 billion vertices, which can happen a lot more often than you'd think, then it causes a problem. Also, all those extra reads/writes, which may not affect the complexity in analysis, may still take time on some machines, especially if the information is being stored externally.

I hope this helps someone in the future, because I had a devil of a time finding all this information, then piecing the bits I got from here, there, and everywhere together to form this. I'm blaming the internet and lack of sleep.

这篇关于如何在Dijkstra算法中使用二进制堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！