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

Question

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

Answer 1

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

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

谈论维护邻居的邻接列表作为斐波那契堆结构的一部分几乎是无稽之谈。

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