使用斐波那契堆，是否可以/容易地表示邻居以及最小距离
我正在尝试设计一个带有斐波那契堆的 dijkstras 实现。我想了解的是，除了 O(logn) （带删除）中的最小距离之外，是否可以表示任何给定节点的邻居？或者这违反了斐波那契堆结构？否则我将不得不建立一个邻居列表以及一个斐波那契堆。
I am trying to devise an implementation of dijkstras with fibonacci heaps. What I am trying to understand is if it is possible to represent, other than the minimum distance in O(logn) (with delete) but the neighbors of any given node? Or does this violate the fibonacci heap structure? Otherwise I would have to build a neighbor-list aswell as a fibonacci heap.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你似乎不明白斐波那契堆是什么！
该结构独立于 Dijkstra 或任何其他最短路径算法，并且仅用于通过加快获取距离最小的顶点的时间来加速 Dijkstra 算法。
谈论维护邻居的邻接列表作为斐波那契堆结构的一部分几乎是无稽之谈。
当然，您始终可以维护与该顶点对应的堆节点（从技术上讲，这不是堆结构的一部分）中每个顶点对应的邻居列表。
You don't seem to understand what fibonacci heaps are!
This sturcture is independent of Dijkstra or any other shortest path algorithm, and is only used to speed up Dijkstra's algorithm, by speeding up the time to get the vertex with smallest distance.
Talking about maintain the adjacency list of neighbours as part of the the fibonacci heap structure borders on nonsense.
Of course, you could always maintain the list of neighbours corresponding to each vertex in the heap node (which is technically, not part of the heap structure) corresponding to that vertex..