Каковы различия между алгоритмом всех кратчайших путей NetworkX и алгоритмом scipy floyd warshall? Есть ли причины предпочесть одно другому? Какой самый быстрый?
Вопрос
NetworkX против Scipy все алгоритмы кратчайшего пути
- Согласно источнику NetworkX, они используют алгоритм, описанный в Р. Седжвик, Алгоритмы в C, часть 5: Алгоритмы графов, Addison Wesley Professional, 3-е изд., 2001. github.com/networkx/networkx/blob/ drum 05.05.2014
- Я сравнил scipy и networkx. Тестирование на случайной плотной матрице numpy.random.exponential(size=(1000,1000)) Я обнаружил, что scipy.sparse.csgraph.floyd_warshall() примерно в 10 раз быстрее, чем networkx.algorithms.floyd_warshall_numpy. Другая функция networkx.algorithms.floyd_warshall не была завершена в течение разумного времени. Colonel Panic 30.04.2017
Ответы
Ответ 1 · рейтинг 2 · Joel
(для тех, кто не знает, что алгоритм numpy floyd-warshall доступен в networkx)
Сетьx описание floyd_warshall_numpy гласит:
Алгоритм Флойда подходит для поиска кратчайших путей в плотных графах или графах с отрицательными весами, когда алгоритм Дейкстры не работает. Этот алгоритм все еще может потерпеть неудачу, если есть отрицательные циклы. Он имеет время работы O (n ^ 3) с рабочим пространством O (n ^ 2).
networkx single_source_shortest_path лучше работает на разреженных графах. Вы должны знать, что если вы используете различные алгоритмы "shortest_path", они игнорируют веса ребер. Различные алгоритмы Дейкстры включают веса ребер.
Более подробное описание здесь.
Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.