python中有没有比networkx更高效的计算最短路径问题的方法？

Question

我正在使用 networkx 和 single_source_dijkstra.

计算加权图上从一个源到一个目标的最短路径

但是，我运行陷入内存问题。

有没有更有效的计算方法？ Networkx 的替代品？看我的代码：

   cost, shortestpath = nx.single_source_dijkstra(graph, startpointcoords, secondptcoords,cutoff=10000000)

Answer 1

显然 networkx 的 A* 算法效率更高。然后我用我发布的 dijkstra 算法计算结果路径的长度。

Answer 2

也许尝试使用其他算法？您的图形可能有太多顶点但边很少，在这种情况下您可以使用 Bellman-Ford bellman_ford_path() link in networkX

另一个解决方案是使用另一个 python 包，例如 this question 的答案有不同的可能库。

最后的解决方案是实现自己的算法！也许是 Gabow 的算法，但你必须非常高效，例如将 numpy 与 numba

一起使用

Answer 3

双向 dijkstra 算法应该会产生显着的改进。这里是 the documentation.

一个很好的类比是在 3D 中：将一个气球放在 x 点并展开它直到它到达 y 点。您放入的空气量与它们之间距离的立方成正比。现在在每个点放一个气球并给它们充气直到它们接触。合并后的空气量仅为原来的1/4。在更高维度（与大多数网络更接近的类比）中，减少更多。