NetworkX与Scipy所有最短路径算法的比较

Question

NetworkX与Scipy所有最短路径算法的比较

4

NetworkX的全最短路径算法和scipy的弗洛伊德-沃舍尔算法有什么区别？是否有理由更喜欢其中之一？哪个更快？

- user1507844

根据NetworkX的源代码，他们使用了R. Sedgewick在《C语言算法（第五部分）：图形算法》（Addison Wesley Professional，第三版，2001年）中发现的算法。 https://github.com/networkx/networkx/blob/7d9682a07dcae30acab3c4841e33d31f727a3fb2/networkx/algorithms/simple_paths.py - drum

我比较了scipy和networkx。在一个随机密集矩阵numpy.random.exponential(size=(1000,1000))上测试，我发现scipy.sparse.csgraph.floyd_warshall()比networkx.algorithms.floyd_warshall_numpy快大约10倍。另一个函数networkx.algorithms.floyd_warshall在合理的时间内无法完成。 - Colonel Panic

2个回答

0

Networkx更易于使用，但在我的有限经验中，scipy在最短路径问题上速度更快。

- Tobia Marcucci

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joel · Accepted Answer

对于那些不知道的人，numpy的弗洛伊德-沃尔什算法在networkx中可用。

networkx floyd_warshall_numpy的description说明如下：

弗洛伊德算法适用于查找稠密图或带有负权重的图的最短路径，当Dijkstra算法失败时。如果存在负循环，该算法仍可能失败。它的运行时间为O(n^3)，运行空间为O(n^2)。

networkx single_source_shortest_path算法在稀疏图上效果更好。您应该知道，如果使用各种“shortest_path”算法，则会忽略边缘权重。各种Dijkstra算法包括边缘权重。

更多描述here。