Dijkstra算法与堆。如何更新后放松堆？ [英] Dijkstra with a heap. How to update the heap after relaxation?

问题描述

我想实现Dijkstra算法。

 的foreach距离d
   D = INFINITY
 D [来源] = 0

 create_heap_based_on_Distances（）;

 而（真）
   bestedge =堆[0]

   remove_minimum_from_heap //这将是堆[0]

   bestedge中的foreach邻接
      如果（重量+ bestedge_distance＆LT; current_distance）
      {
          current_distance =重量+ bestedge_distance

          //现在我要更新堆，我该怎么办呢？
      }
   如果（heap_empty）破
 

所以，在放松，我怎么能更新堆，所以它必须按照正确的顺序？我没有对在该步骤该节点的堆的索引。这是否意味着我要创建一个新的数组像节点[边缘] = heapIndex ，这样我就可以得到该节点的堆的指数？但似乎非常低效的，因为我需要再更新 insert_to_heap ， remove_minimum 功能。

C或JAVA code是好的。

解决方案

  

这是否意味着我必须创建一个新的数组像节点[边缘] = heapIndex，这样我就可以得到一个堆的索引节点？

是的。

  

但它似乎非常低效的，因为我需要再更新insert_to_heap，remove_minimum功能。

数组的更新是非常便宜的，无论在理论上还是在实践中，你只需要做一些这些每堆的运行，所以这不是低效率的。另外，相比于图数据结构的存储成本这样的阵列的存储器的使用情况是很便宜。

I am trying to implement Dijkstra algorithm.

 foreach distance d
   d = INFINITY
 d[source] = 0

 create_heap_based_on_Distances();

 while(true)
   bestedge = heap[0]

   remove_minimum_from_heap //it will be heap[0]

   foreach adjacency of bestedge
      if (weight + bestedge_distance < current_distance)
      {
          current_distance = weight + bestedge_distance

          // Now I have to update heap, how can I do that?
      }
   if (heap_empty) break

So, in the relaxation, how can I update the heap, so it would have the correct order? I don't have the heap's index for that node in that step. Does that mean I have to create a new array like nodes[edge] = heapIndex, so I could get a heap's index for that node? But it seems very inefficient as I need then to update insert_to_heap, remove_minimum functions.

C or JAVA code is okay.

解决方案

Does that mean I have to create a new array like nodes[edge] = heapIndex, so I could get a heap's index for that node?

Yes.

But it seems very inefficient as I need then to update insert_to_heap, remove_minimum functions.

Array updates are very cheap, both in theory and in practice, and you only have to do a few of those per heap operation, so this is not inefficient at all. Also, the memory usage of such an array is very cheap compared to the storage cost of a graph data structure.

这篇关于Dijkstra算法与堆。如何更新后放松堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！