如何存储Dijkstra算法的相邻节点？

发布时间：2020-12-16 07:02:21 所属栏目：百科来源：网络整理

导读：关于Dijkstra算法的大多数文章仅关注应该使用哪种数据结构来执行节点的“放松”. 我打算使用一个在O(m log(n))上运行的min-heap.我相信. 我真正的问题是我应该使用什么数据结构来存储每个节点的相邻节点？我正在考虑使用邻接列表,因为我可以在O(deg(u))中找

关于Dijkstra算法的大多数文章仅关注应该使用哪种数据结构来执行节点的“放松”.

我打算使用一个在O(m log(n))上运行的min-heap.我相信.

我真正的问题是我应该使用什么数据结构来存储每个节点的相邻节点？
我正在考虑使用邻接列表,因为我可以在O(deg(u))中找到u上的所有相邻节点,这是最快的方法吗？

这将如何改变算法的运行时间？

使用Dijkstra的算法,您只需循环一个节点的邻居列表,因此在每个节点(如在邻接列表中)存储相邻节点(或简单地在全局列表中的索引)的简单数组或链表就足够了.

这将如何改变算法的运行时间？ – 与什么相比？我很确定算法复杂性假定了邻接列表实现. The running time is O(edges + vertices * log(vertices)).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!