Какова самая быстрая реализация Dijkstra, которую Вы знаете (в C++)?
У меня была эта ошибка с тех пор, как я обновил свой компьютер и обновил до 3.1+ (что было сделано в то же время). Я получал список успехов / неудач в виде дерева, но когда произошел сбой, он просто остановился, но на самом деле он не перечислял ошибки в дереве. Мне пришлось просмотреть полные журналы отладки, чтобы выяснить, где происходили какие-либо проблемы.
Я полагаю, что проблема связана с пробелом в моем имени пользователя, Android Studio загружает SDK в папку по умолчанию «C: \ Users \ имя пользователя \ AppData \ Local \ Android \ sdk». Я заметил, что некоторые окна конфигурации жалуются на пространство в этом месте, поэтому я переместил свой SDK в «C: \ Dev \ Android \ sdk», и теперь я снова вижу ошибки Java в нижней части дерева.
4 ответа
Лучшие реализации, известные для дорожных сетей (> 1 миллиона узлов), имеют время запроса, выраженное в микро секундах. Для получения более подробной информации см. 9-ю задачу по внедрению DIMACS (2006 г.). Обратите внимание, что это, конечно, не просто Дейкстра, поскольку все дело в том, чтобы получить результаты быстрее.
Возможно, я не отвечаю на ваш вопрос. Я хочу сказать, зачем использовать Dijkstra, когда есть гораздо более эффективные алгоритмы для вашей проблемы. Если ваш граф выполняет свойство треугольника (это евклидов граф)
| ab | + | bc | > | ac |
(расстояние от узла a до узла b плюс расстояние от узла b до узла c больше, чем расстояние от узла a до узла c), тогда вы можете применить алгоритм A *. Этот алгоритм довольно эффективен. В противном случае рассмотрите возможность использования эвристики. Реализация - не главная проблема. Используемый алгоритм имеет значение.
В последний раз, когда я проверял, алгоритм Дейкстры возвращает оптимальное решение. Все «истинные» реализации Дейкстры должны каждый раз возвращать один и тот же результат.
Точно так же асимптотический анализ показывает нам, что незначительные оптимизации конкретных реализаций не будут существенно влиять на производительность при увеличении размера входных данных.
Это будет зависеть от много вещей. Насколько хорошо вы знаете свои входные данные? Он плотный или разреженный? Это изменит самые быстрые версии алгоритма.
Если он плотный, просто используйте матрицу. Если его немного, вы можете посмотреть на более эффективные структуры данных для поиска следующей ближайшей вершины.