NetworkX vs Scipy所有最短路径算法 [英] NetworkX vs Scipy all shortest path algorithms
问题描述
NetworkX所有最短路径算法和scipy floyd warshall算法之间有什么区别?有什么理由要优先于另一个吗?哪个最快?
What are the differences between the NetworkX all shortest paths algorithm and the scipy floyd warshall algorithm? Are there any reasons to prefer one over another? Which is fastest?
推荐答案
(对于那些不知道numpy floyd-warshall算法在networkx中可用的人)
(for those who aren't aware the numpy floyd-warshall algorithm is available in networkx)
The networkx description of floyd_warshall_numpy states:
当Dijkstra算法失败时，弗洛伊德(Floyd)算法适合在稠密图形或负权重图形中查找最短路径.如果存在负周期，则该算法仍会失败.它的运行时间为O(n ^ 3)，运行空间为O(n ^ 2).
Floyd’s algorithm is appropriate for finding shortest paths in dense graphs or graphs with negative weights when Dijkstra’s algorithm fails. This algorithm can still fail if there are negative cycles. It has running time O(n^3) with running space of O(n^2).
networkx single_source_shortest_path在稀疏图上效果更好.您应该意识到，如果使用各种"shortest_path"算法，这些算法将忽略边缘权重.各种Dijkstra算法都结合了边缘权重.
The networkx single_source_shortest_path works better on sparse graphs. You should be aware that if you use the various "shortest_path" algorithms, these ignore edge weights. The various Dijkstra algorithms incorporate edge weights.
在此处有更多描述.
There is more description here.
这篇关于NetworkX vs Scipy所有最短路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
