有人可以解释一下HeapDesc在 ShaneSaunders Dijkstra 算法中的重要性以及它是如何在这里使用的吗？一般来说，我知道 Dijkstra 算法是如何工作的。但是，我没有在实现中得到堆部分。
它是一个大代码。因此，如果您想查看它，我会发布一个链接。
这里去http://www.cosc.canterbury.ac.nz/research/RG/alg/dijkstra.cpp
问问题
2242 次
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 回答