NetworkX против Scipy все алгоритмы кратчайшего пути

Каковы различия между алгоритмом всех кратчайших путей NetworkX и алгоритмом scipy floyd warshall? Есть ли причины предпочесть одно другому? Какой самый быстрый?


python scipy shortest-path networkx
person user1507844    schedule 05.05.2014    source источник
comment
Согласно источнику NetworkX, они используют алгоритм, описанный в Р. Седжвик, Алгоритмы в C, часть 5: Алгоритмы графов, Addison Wesley Professional, 3-е изд., 2001. github.com/networkx/networkx/blob/   -  person drum    schedule 05.05.2014
comment
Я сравнил scipy и networkx. Тестирование на случайной плотной матрице numpy.random.exponential(size=(1000,1000)) Я обнаружил, что scipy.sparse.csgraph.floyd_warshall() примерно в 10 раз быстрее, чем networkx.algorithms.floyd_warshall_numpy. Другая функция networkx.algorithms.floyd_warshall не была завершена в течение разумного времени.   -  person Colonel Panic    schedule 30.04.2017

Ответы (1)


arrow_upward
2
arrow_downward

(для тех, кто не знает, что алгоритм numpy floyd-warshall доступен в networkx)

Сетьx описание floyd_warshall_numpy гласит:

Алгоритм Флойда подходит для поиска кратчайших путей в плотных графах или графах с отрицательными весами, когда алгоритм Дейкстры не работает. Этот алгоритм все еще может потерпеть неудачу, если есть отрицательные циклы. Он имеет время работы O (n ^ 3) с рабочим пространством O (n ^ 2).

networkx single_source_shortest_path лучше работает на разреженных графах. Вы должны знать, что если вы используете различные алгоритмы «shortest_path», они игнорируют веса ребер. Различные алгоритмы Дейкстры включают веса ребер.

Более подробное описание здесь.

person Joel    schedule 15.12.2014