Каков наилучший алгоритм кратчайшего пути из одного источника для соревнований по программированию?

Question

Я работал над этой проблемой графика из набора задач UVa. Это проблема одного источника с кратчайшими путями без отрицательных весов ребер. Из того, что я понял, алгоритм с наилучшим временем выполнения big-O для таких задач - это Дейкстра с кучей Фибоначчи в качестве очереди приоритетов, хотя практически говоря, двоичная куча проще в реализации и работает довольно хорошо.

Однако может показаться, что даже двоичная куча занимает довольно много времени, а в соревновании время ограничено. Мне известно, что STL предоставляет некоторые алгоритмы кучи и очереди с приоритетами, но они, похоже, не обеспечивают функцию уменьшения ключа, которая нужна Дейкстре. Или я здесь не прав?

Кажется, что другая возможность - просто не использовать Дейкстры. В этой ветке форума есть люди, утверждающие, что они решили вышеупомянутую проблему с помощью поиска в ширину / Bellman-Ford, который гораздо проще кодировать. (Правка: OTOH, у Дейкстры с несортированным массивом для очереди приоритетов истекло время ожидания.) То, что BFS / Bellman-Ford работал, меня немного удивило, так как я думал, что размер ввода был довольно большим. Я предполагаю, что разные проблемы потребуют решений различной сложности, но мой вопрос заключается в том, как часто мне нужно будет использовать Дейкстру на таких соревнованиях? Стоит ли больше практиковаться в более простых, но медленных алгоритмах?

Answer 1

Если вы можете придумать хорошую эвристику лучше всего, я бы попробовал использовать A *

Answer 2

Исходя из собственного опыта, мне никогда не требовалось реализовывать алгоритм Дейкстры с кучей в конкурсе по программированию. Вы можете уйти большую часть времени, используя более медленный, но достаточно эффективный алгоритм. Вы можете использовать лучшую реализацию Dijkstra для решения проблемы, которая предполагает другой / более простой алгоритм, но это редкий случай.

Answer 3

Вы можете реализовать Dijkstra, используя кучи / очереди приоритетов без уменьшения ключа (я думаю) O ((E + V) log V). Если вы хотите уменьшить ключ, просто добавьте новую запись в вашу приоритетную очередь (оставив старую запись в очереди) и обновите ваш массив с расстояниями. Когда вы убираете минимальный элемент из своей очереди, сначала убедитесь, что он равен вашему массиву расстояний, если нет, то это ключ, который вы хотели уменьшить, поэтому просто проигнорируйте его.

Answer 4

Dijkstra и простая очередь с приоритетами должны хорошо работать даже для больших наборов данных. Если вы практикуете, вы можете попробовать это также с двоичной кучей и сравнить производительность. Конечно, я думаю, что создание кучи Фибоначчи - это небольшая ограниченность, и я бы предпочел сначала попрактиковаться в других структурах данных и алгоритмах.

Интересно, что использование очереди с приоритетами эквивалентно поиску в ширину с эвристикой поиска наилучшего текущего решения в первую очередь.

Answer 5

Библиотека Boost Graph , похоже, имеет реализации как для Дейкстры, так и для Беллмана-Форда.