4

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?

user1507844
  • 5,973
  • 10
  • 38
  • 55
  • According to the source for NetworkX, they are using the algorithm found in R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms", Addison Wesley Professional, 3rd ed., 2001. https://github.com/networkx/networkx/blob/7d9682a07dcae30acab3c4841e33d31f727a3fb2/networkx/algorithms/simple_paths.py – drum May 05 '14 at 02:32
  • I compared scipy and networkx. Testing on a random dense matrix `numpy.random.exponential(size=(1000,1000))` I found `scipy.sparse.csgraph.floyd_warshall()` is around 10x faster than `networkx.algorithms.floyd_warshall_numpy`. The other function `networkx.algorithms.floyd_warshall` did not complete within a reasonable time. – Colonel Panic Apr 30 '17 at 20:46

2 Answers2

2

(for those who aren't aware the numpy floyd-warshall algorithm is available in networkx)

The networkx description of floyd_warshall_numpy states:

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).

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.

Community
  • 1
  • 1
Joel
  • 22,598
  • 6
  • 69
  • 93
0

Networkx is easier to use but, in my limited experience, scipy is much faster for shortest-path problems.

Tobia Marcucci
  • 204
  • 1
  • 7