NetworkX与Scipy的所有最短路径算法
NetworkX的所有最短路径算法和scipy的Floyd-Warshall算法有什么区别？有没有理由选择其中一个而不是另一个？哪个更快？
2 个回答
0
Networkx用起来比较简单，但根据我有限的经验，scipy在解决最短路径问题时要快得多。
2
（对于那些不知道的人，numpy的Floyd-Warshall算法在networkx中是可以使用的）
networkx对floyd_warshall_numpy的描述是：
Floyd算法适合用来寻找稠密图（也就是节点很多、连接也很多的图）或有负权重的图中的最短路径，当Dijkstra算法不适用时，这个算法仍然可以使用。不过，如果图中有负循环，算法可能会失败。它的运行时间是O(n^3)，而占用的空间是O(n^2)。
networkx的single_source_shortest_path在稀疏图（节点少、连接也少的图）上表现得更好。你需要注意的是，如果你使用各种“最短路径”算法，它们会忽略边的权重。而不同的Dijkstra算法则会考虑边的权重。
这里还有更多的描述在这里。