使用斐波那契堆，是否可以/容易地代表邻居和最小距离

Question

我试图设计一个斐波那契堆dijkstras的实现。我试图理解的是，如果除了O（logn）（带有删除）中的最小距离以外，还可以表示任何给定节点的邻居吗？或者这是否违反斐波那契堆结构？否则，我将不得不建立一个邻居列表以及斐波那契堆。

Answer 1

你似乎不明白斐波那契堆是什么！

这是内在张力结构Dijkstra算法或任何其他最短路径算法的独立，并只用于加快Dijkstra算法，通过加速的时间来获得与最小距离顶点。

谈论维护作为斐波那契堆结构的一部分的邻居邻接列表的边界是无意义的。

当然，您始终可以维护对应于该顶点的堆节点（技术上，不是堆结构的一部分）中每个顶点的邻居列表。