聚合物模拟-2个节点之间的最短路线,适用于所有节点

这个问题被称为“所有对最短路径”。

一般图表

对于一般图,传统上用O(n ^3. )时间使用 Floyd-Warshall Algorithm ,其中“n”是图中的节点数。

请注意,所需的空间和产生的输出大小为O(n ^2. ). 对于大型图形来说,这是一个很大的输出。由于系统内存的限制,您的最大图形大小可能会达到100000左右。

还要注意n ^3. 生长得相当快。如果你用C或等效语言编写,那么对于一个有1000个节点的图来说,它会非常快(几毫秒),但对于100000个节点来说,可能需要几个小时。如果你用较慢的语言编写,那么它会较慢,但这是一种常见的算法,所以你可能会找到一个快速的库实现。 scipy has one 例如。

稀疏图形

对于稀疏图,其中每个节点平均只有几条边,BFS比Floyd Warshall快得多,取O(n ^2. )时间。

与上述情况相比,每个节点的平均边数为4条或更少,您应该能够在几秒钟内计算出100000个节点的所有最短路径长度。

根据您的描述,听起来您尝试了BFS,但对每对节点分别进行了错误的操作。这比你需要做的工作要多得多,因为从单个源节点进行一次BFS搜索将找到到的最短路径 全部的 其他节点。你只需要同时进行n次搜索。