c - 如何为 Dijkstra 算法存储相邻节点？

Question

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

我将使用O(m log(n))我相信的最小堆。

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

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

Answer 1

对于算法本身，我认为您应该以图形的紧凑表示为目标。如果每个节点有很多链接，矩阵可能是最好的，但通常邻接列表将占用更少的空间，因此缓存未命中更少。

可能值得看看您是如何构建图表的，以及您在其上执行的任何其他操作。

Answer 2

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

How will that change the running time of the algorithm?- 与什么相比？我很确定算法复杂性假设邻接列表实现。运行时间为O(edges + vertices * log(vertices))。