Dijkstra的算法:内存消耗

Question

我根据本网站上的代码实现了Dijkstra的算法.基本上,我有许多节点(比如10000),每个节点可以有1到3个连接到其他节点.

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

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

有没有人知道实现算法以减少内存占用的另一种方法,还是有另一种算法使用更少的内存？

Answer 1

根据您上面的评论,您使用距离矩阵 表示图形的边缘long dist[GRAPHSIZE][GRAPHSIZE].这将占用O(n^2)内存,这对于大值来说太过分了n.当你只有少量的边时,它在执行时间方面也不是一个好的表示:它会导致Dijkstra的算法花费O(n^2)时间(n节点的数量),当它可能更快时,取决于数据结构用过的.

因为在您的情况下,您说每个节​​点仅连接到最多3个其他节点,您不应该使用此矩阵:相反,对于每个节点,您应该存储它所连接的节点的列表.然后,当您想要遍历节点的邻居时,您只需要遍历此列表.

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