堆在Dijkstra算法

有人可以解释什么是什么重要性HeapDesc在ShaneSaunders Dijkstra算法和它是如何使用在这里？一般来说，我知道Dijkstra算法是如何工作的。但是，我并没有实现堆部分。堆在Dijkstra算法

它是一个很大的代码。因此我发布了一个链接，如果你想看看它。

2013-01-05 NRK

什么部分你不清楚？ HeapDesc的定义或如何使用？ – Max

我想知道两个 – NRK

Dijkstra's algorithm涉及到大量“成本最低的路径”查找。

最小或最大查找是Heap针对（O（1））进行了优化的，这就是它被使用的原因。

至于HeapDesc本身，它似乎是a factory method，用于分配堆对象。

Heap *newInstance(int n) const { return new T(n); }; // from heap.h

2013-01-05 11:09:43

但是，这在代码中代表什么呢？ heap = heapDD-> newInstance（nn）; 以及他如何定义它 – NRK

@NRK我不确定'HeapDesc'本身是什么，但它看起来像一个分配器或工厂方法用于创建一个堆。您需要查看“heap/heap.h”。 –

在Dijkstra中，您需要一个高效的数据结构，为您提供可让您到达另一个顶点的最低成本边缘。

Heap恰好是一种数据结构，它允许您存储边缘集合并以最低成本高效地检索边缘。

2013-01-05 11:10:31 mariosangiorgio

我可能会改变*“数据结构”*为*“一个数据结构”*虽然 – Alexander

你是对的。我刚刚编辑了我的回答 – mariosangiorgio

感谢您的答复......明白了。 – NRK

HeapDesc可能实现了工厂设计模式来创建不同类型的堆。如果您检查文件http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.h，您会注意到构造函数中的堆变量是Heap类型的对象。

2013-01-05 11:18:13 ipinak

嘿谢谢。这将是很好的知道 – NRK

回答