c++ - Dijkstra 算法 : memory consumption

Question

我有一个 Dijkstra 算法的实现，基于 this website 上的代码.基本上，我有许多节点(比如 10000 个)，每个节点可以有 1 到 3 个与其他节点的连接。

节点在 3d 空间内随机生成。连接也是随机生成的，但是它总是首先尝试找到与其最近邻居的连接，然后慢慢增加搜索半径。每个连接的距离为 1。 (我怀疑这是否重要，但这只是背景)。

在这种情况下，该算法只是用于找到从起点到所有其他节点的最短跳数。它适用于 10,000 个节点。我遇到的问题是，随着节点数量的增加，比如接近 200 万，我在尝试构建图表时用尽了我所有的计算机内存。

有谁知道实现该算法以减少内存占用的替代方法，或者是否有另一种使用更少内存的算法？

Answer 1

根据您上面的评论，您用 distance matrix 表示图形的边缘长距离[GRAPHSIZE][GRAPHSIZE]。这将占用 O(n^2) 内存，这对于较大的 n 值来说太多了。当您只有少量边时，它在执行时间方面也不是一个很好的表示:它会导致 Dijkstra 的算法花费 O(n^2) 时间(其中 n 是节点数)，它可能会更快，具体取决于所使用的数据结构。

由于在您的情况下您说每个节​​点最多只能连接到 3 个其他节点，因此您不应该使用此矩阵:相反，对于每个节点，您应该存储它所连接的节点的列表。那么当你想遍历一个节点的邻居时，你只需要遍历这个列表。

在某些特定情况下，您甚至不需要存储此列表，因为可以在需要时为每个节点计算它。例如，当图是一个网格并且每个节点都连接到相邻的网格节点时，很容易在运行中找到一个节点的邻居。