0

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

它是一个大代码。因此，如果您想查看它，我会发布一个链接。

这里去http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.cpp

4

3 回答 3

1

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

堆正是一种数据结构，它允许您存储一组边并以最低成本有效地检索一个。

于 2013-01-05T11:10:31.067 回答
1

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

查看本文以了解工厂设计模式。 http://en.wikipedia.org/wiki/Factory_method_pattern

于 2013-01-05T11:18:13.477 回答
0

Dijkstra 的算法涉及大量“最低成本路径”查找。

最小或最大查找是堆优化的对象（ O(1) ），这就是使用它的原因。

就HeapDesc其本身而言，它只是一个工厂方法，用于分配一个堆对象。

Heap *newInstance(int n) const { return new T(n); }; // from heap.h
于 2013-01-05T11:09:43.150 回答