3
В чем разница между алгоритмом NetworkX all shortest paths и алгоритмом scipy floyd warshall? Есть ли какие-то причины предпочесть друг другу? Что быстрее?NetworkX vs Scipy все алгоритмы кратчайшего пути
A
ответ
2
(для тех, кто не знает алгоритм NumPy Флойда-Воршалла доступен в NetworkX)
NetworkX description из floyd_warshall_numpy состояний:
алгоритм Флойда подходит для нахождения кратчайших путей в плотной графики или графики с отрицательными весами, когда алгоритм Дейкстры терпит неудачу. Этот алгоритм может по-прежнему терпеть неудачу, если есть отрицательные циклы. Он имеет время работы O (n^3) с пробегом O (n^2).
Networkx single_source_shortest_path работает лучше на разреженных графиках. Вы должны знать, что если вы используете различные алгоритмы «shortest_path», они игнорируют вес границ. Различные алгоритмы Дейкстры включают в себя веса ребер.
Описание: here.
Смежные вопросы
- 1. Алгоритмы скалолазания и одиночные пары кратчайшего пути
- 2. комбинация, алгоритмы кратчайшего пути и Python
- 3. OrientDB: все пары кратчайшего пути
- 4. Python: NetworkX Нахождение кратчайшего пути, который содержит данный список узлов
- 5. Ограничения на Dijkstra, Bellman ford и топологические алгоритмы кратчайшего пути?
- 6. алгоритм кратчайшего пути через все края
- 7. Все пары кратчайшего пути - теплый перезапуск?
- 8. алгоритм кратчайшего пути или маршрута
- 9. алгоритм кратчайшего пути в android
- 10. Непрерывный пробел кратчайшего пути
- 11. Нахождение кратчайшего замкнутого пути
- 12. Корректировка алгоритма кратчайшего пути
- 13. кратчайшего алгоритм пути Дейкстры
- 14. Алгоритм кратчайшего пути Флойда?
- 15. кратчайшего пути в графе
- 16. Программа кратчайшего пути Python
- 17. Алгоритм кратчайшего пути Djikstra
- 18. Примеры кратчайшего пути Giraph
- 19. Получение кратчайшего угла пути
- 20. Проектирование кратчайшего алгоритма пути
- 21. Сохранение кратчайшего пути
- 22. расчет алгоритма кратчайшего пути
- 23. кратчайшего пути алгоритм ошибка
- 24. алгоритмы преобразования расстояния в scipy
- 25. Networkx - Наименьшая длина пути
- 26. Требование дерева кратчайшего пути (график)
- 27. Алгоритм кратчайшего пути AFP Dijkstra
- 28. Вероятность и алгоритм кратчайшего пути
- 29. ускорение алгоритма поиска кратчайшего пути
- 30. Алгоритм кратчайшего пути в частичном графике
Согласно источнику для NetworkX, они используют алгоритм, найденный в R. Sedgewick, «Алгоритмы в C, часть 5: Алгоритмы графа», Addison Wesley Professional, 3-е изд., 2001. https: // github. com/networkx/networkx/blob/7d9682a07dcae30acab3c4841e33d31f727a3fb2/networkx/algorithmms/simple_paths.py – drum
Я сравнивал scipy и networkx. Тестирование на случайной плотной матрице 'numpy.random.exponential (size = (1000,1000))' Я нашел 'scipy.sparse.csgraph.floyd_warshall()' примерно в 10 раз быстрее, чем 'networkx.algorithms.floyd_warshall_numpy'. Другая функция 'networkx.algorithms.floyd_warshall' не завершилась в течение разумного периода времени. –