7

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

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

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

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

4

3 回答 3

8

根据您上面的评论，您用距离矩阵 long dist[GRAPHSIZE][GRAPHSIZE]表示图形的边缘。这将占用O(n^2)内存，对于较大的n. 当您只有少量边时，它在执行时间方面也不是一个很好的表示：它会导致 Dijkstra 的算法花费O(n^2)时间（n节点数在哪里），而它可能会更快，具体取决于数据结构用过的。

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

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

于 2012-12-26T13:35:08.893 回答
4

如果您真的负担不起内存，即使您的图形表示最小化，您也可以开发Dijkstra算法的变体，考虑分而治之的方法。

这个想法是将数据分成小块，因此您将能够在每个块中针对其中的每个点执行 Dijkstra 算法。

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

例如，考虑以下几点：

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

您可以选择最接近给定节点的点，例如，在两跳内，然后将解作为扩展图的一部分，将前一个点视为一组点，距离等于结果的距离迪杰斯特拉解决方案。

假设您从D：

  • 在给定的范围内选择closest pointsto ；Dnumber of hops
  • 对所选条目使用 Dijkstra 算法，从D;
  • 将解决方案用作图，其中中心节点D和最短路径中的最后一个节点作为直接链接到的节点D；
  • 扩展图，重复算法，直到所有节点都被考虑在内。

虽然这里有一个昂贵的额外处理，但您可以超越内存限制，并且，如果您有其他一些机器，您甚至可以分配这些进程。

请注意，这只是流程的想法，我描述的流程不一定是最好的方法。在寻找分布式 Dijkstra 算法时，您可能会发现一些有趣的东西。

于 2012-12-26T12:03:55.350 回答
1

我非常喜欢 boost::graph。它的内存消耗非常好（我在具有 1000 万个节点和 2Gb 内存的道路网络上使用过它）。

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

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

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

于 2012-12-26T13:49:39.867 回答