有效计算图表中达到一定限制的距离

我正在尝试计算一个大图中（大约 160k 个节点）中所有节点对之间的距离（最短路径的长度）。我已经尝试了几种实现方式，例如 Python 中的 igraph distances() in R 、NetworkX 的 shortest_path_lengths() ，以及 Dijkstra 算法的一些自制实现。然而，这个计算需要很长时间（在非常大的机器上大约需要 3-4 小时），我想知道是否有更有效的方法来做到这一点。基本上：目前计算图中所有距离的最有效的实现是什么，您知道我可以从 R 或 Python 调用？ 另一个提示： 我的数据中的一个因素是图表中的距离要么很小（<10）要么无限大，所以我想知道是否有一种方法利用它来使计算更快，即在距离 10 之后停止计算？是否有一些实现可以让我轻松添加“停止”条件来计算距离？ 任何帮助是极大的赞赏 ：）

当然，计算大图中所有成对最短路径的长度可能是一项计算量很大的任务。让我们来探讨一些使之更快的策略：

1. 利用稀疏性： 由于的图很大且距离稀疏（小于 10 或无限大），因此稀疏矩阵表示将非常有益。igraph 和 NetworkX 都支持稀疏矩阵，这可以显着减少内存使用量并加快计算速度。

2. 截断 Dijkstra 算法： 正如所指出的，在达到距离阈值时停止 Dijkstra 算法可以节省计算量。可以修改 Dijkstra 算法或使用允许提供“截止”或“限制”参数的库实现。这会在找到指定限制内的路径后停止搜索，从而潜在地加快计算速度。

3. 批量 Dijkstra 算法： 与其对每个节点分别运行 Dijkstra 算法，不如考虑同时从一组节点运行它的变体。这可以更有效地利用缓存并减少开销。

4. 近似算法： 如果可以容忍一些近似值，则有可以提供对所有成对距离的快速估计的算法，例如：

5. landmark-based 算法： 通过预先计算到一组选定“地标”节点的距离，可以估计其他节点之间的距离。

6. Dijkstra 的双向搜索： 从源节点和目标节点同时运行 Dijkstra 算法，并在两者相遇时停止。

7. 并行化： 所有成对最短路径计算可以很容易地并行化，因为每个节点对的计算都是独立的。利用多核处理器或分布式计算框架（如 Apache Spark）可以显着减少整体运行时间。

库和实现：

• igraph（R 和 Python）： igraph 是一个用于处理图的强大库。它提供各种最短路径算法，包括 Dijkstra 和 A*，以及对稀疏矩阵表示的支持。可以使用 distances(graph, limit=10) 参数在 igraph 中指定距离限制。

• NetworkX（Python）： NetworkX 是另一个用于处理图的出色 Python 库。它还支持 Dijkstra 算法及其变体，以及稀疏矩阵。可以在 NetworkX 中使用 shortest_path_length(graph, source=None, target=None, cutoff=10) 参数设置截止值。

• SciPy（Python）： SciPy 库的 scipy.sparse.csgraph 模块提供了用于稀疏图的有效最短路径算法，包括 Dijkstra 和 Floyd-Warshall。

建议：

• 首先通过使用稀疏矩阵表示并设置距离截止值（例如，使用 igraph 或 NetworkX）在的数据上尝试截断的 Dijkstra 算法。
• 如果计算时间仍然是一个问题，请探索批量 Dijkstra 算法或近似算法，如 landmark-based 方法。
• 考虑并行化计算以利用多核处理器或分布式计算框架。

请记住，最有效的算法将取决于的图的特定特征和所需的准确度水平。在选择最适合需要的方法之前，最好对不同的方法进行实验。