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

Question

我正在尝试设计一个使用斐波那契堆的dijkstras实现。我试图理解的是，除了O(logn) (带有delete)中的最小距离之外，是否可以表示任何给定节点的邻居？或者这是否违反了斐波那契堆结构？否则，我将不得不构建一个邻居列表以及一个斐波那契堆。

Answer 1

您似乎不了解斐波那契堆是什么！

这种结构独立于Dijkstra或任何其他最短路径算法，仅用于加速Dijkstra算法，通过加速获得距离最小的顶点的时间。

谈到维护邻居的邻接列表作为斐波那契堆结构的一部分，简直就是胡说八道。

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