如何为迪杰斯特拉算法存储相邻节点？

Question

4

大多数关于Dijkstra算法的文章只关注使用哪种数据结构来执行节点"松弛"，我将使用一个运行时间为O(m log(n))的最小堆。

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

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

- Tiago Costa

2个回答

0

使用Dijkstra算法，您只需要循环遍历一个节点的邻居列表一次，因此在每个节点存储相邻节点的简单数组或链表（或者只是它们在全局列表中的索引）（如邻接表）就足够了。

这将如何改变算法的运行时间？ - 与什么进行比较？我相当确定算法复杂度假定使用邻接表实现。运行时间为O（edges + vertices * log（vertices））。

- Bernhard Barker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Patricia Shanahan · Accepted Answer

对于算法本身，我认为你应该针对图的紧凑表示进行优化。如果每个节点有很多链接，那么矩阵可能是最好的选择，但通常邻接表将占用更少的空间，因此会减少缓存未命中率。

值得注意的是，你可能需要查看如何构建图以及在其上执行的任何其他操作。