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

Question

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

我将使用运行在 O(m log(n)) 上的最小堆，我相信。

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

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

Answer 1

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

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