Dijkstra算法：内存消耗

Question

我有一个基于这个网站上的代码实现Dijkstra算法。 我有很多节点（比如10000个），每个节点可以与其他节点有1到3个连接。

这些节点在3D空间中随机生成。 连接也是随机生成的，但总是首先尝试找到最近邻居的连接，然后慢慢增加搜索半径。 每个连接都被赋予距离为1。（我不确定这些是否重要，但这只是背景）

在这种情况下，该算法仅用于找到从起点到所有其他节点的最短跳数，并且对于10,000个节点效果很好。 我遇到的问题是，随着节点数量的增加，比如达到200万个节点时，在构建图形时就会耗尽计算机的所有内存。

有没有人知道实现算法的替代方法来减少内存占用，或者是否有另一个使用更少内存的算法？

- John

---

由于 Dijkstra 算法本身与节点数量成线性比例，我猜测图形表示本身会占用大量内存。您使用哪种数据结构来表示图形？ - Howard

更重要的是，您正在运行什么样的架构？具有几个GB的RAM的PC应该能够存储比2M节点多得多的内容，除非每个节点占用数百字节 - 在这种情况下，您可能需要重新考虑节点信息。 - Mats Petersson

你的代码在构建图阶段可能存在内存泄漏问题。你能否发布你的代码？ - emreakyilmaz

@emreakyilmaz ，代码与我第一篇帖子中网站上的代码几乎相同。 - John

@ Mats Petersson：我的电脑有4GB的内存！正如emreaky所说，也许存在内存泄漏问题。看一下我在问题中发布的链接中的代码，它是否能够处理200万个节点的图形呢？例如，long dist[GRAPHSIZE][GRAPHSIZE]，这不会占用大量内存吗？ - John

@John，看起来你自己解决了——查看interjay的答案以获取有关如何摆脱此数组的详细信息。 - Ivan Vergiliev

Answer 1

根据您上面的评论，您用一个距离矩阵long dist[GRAPHSIZE][GRAPHSIZE]来表示图的边缘。这将占用O(n^2)内存，在n的大值情况下过多。在仅有少量边缘时，这也不是一个执行时间好的表示：这将导致Dijkstra算法花费O(n^2)的时间（其中n是节点数），而它可能更快，这取决于所使用的数据结构。

由于在您的情况下，每个节点只与最多3个其他节点相连，因此不应使用此矩阵：相反，对于每个节点，您应该存储其连接的节点列表。然后，当您想要遍历节点的邻居时，您只需要迭代此列表即可。

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

- interjay

---

Interjay非常感谢您的回答！也感谢其他人的贡献。 - John

Answer 2

如果您即使在图形表示上进行了最小化，仍然无法承受内存成本，您可以开发Dijkstra算法的变体，考虑采用“分而治之”的方法。

这个想法是将数据分割成较小的块，以便您可以在每个块中执行Dijkstra算法，对其中的每个点执行算法。

对于在这些小块中生成的每个解决方案，请将其视为另一个数据块的唯一节点，从该节点开始执行另一个Dijkstra算法。

例如，考虑下面的点：

.B        .C
                  .E
 .A           .D
       .F                   .G

您可以选择距离给定节点最近的点，比如在两个跳之内，然后将其解决方案作为图形扩展的一部分，将前面的点视为仅有一个点集，距离等于Dijkstra解决方案的结果距离。

假设您从 D 开始:

- 选择距离 D 最近的点，跳数不超过给定数量; - 对所选条目使用 Dijkstra 算法，从 D 开始; - 使用解决方案作为一个图形，其中心节点为 D ，最短路径中的最后节点直接连接到 D ; - 扩展图形，重复算法直到考虑所有节点。

尽管这里有一个昂贵的额外处理，但您将能够 超越内存限制 ，而且如果您拥有其他机器，甚至可以 分发 这些进程。

请注意，这只是该流程的想法，我描述的流程未必是最佳方法。您可能会在 寻找分布式 Dijkstra 算法时找到一些有趣的东西。

- Rubens

---

嗨，Rubens，感谢你的回答。分而治之听起来是一个不错的方法。我会先尝试interjay的建议，因为它目前适合我的节点生成和连接存储方式（节点数组，每个节点包含一个连接节点列表）。也许如果达到了某种限制，我可以采用你的方法。谢谢！ - John

@John 很好，你找到了一个建议，它不需要对你已有的太多更改; 如果达到限制，我很乐意帮忙！祝你好运！ - Rubens

Answer 3

我非常喜欢boost::graph。它的内存消耗非常合理（我已经在具有1000万个节点和2GB RAM的道路网络上使用了它）。

它有一个Dijkstra实现，但如果目标是自己实现并理解它，你仍然可以使用它们的图表表示法（我建议邻接表），并将你的结果与他们的结果进行比较，以确保你的结果是正确的。

一些人提到了其他算法。我不认为这会对内存使用产生很大影响，但更可能会影响速度。如果拓扑结构接近街道网络，200万节点从一个节点到所有其他节点的运行时间将少于一秒钟。

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html

- Tristram Gräbener