Comments 8
Плохое объяснение. Особенно с учетом, что статьями про дейкстру завален интернет в целом и хабр в частности.
Вы воспроизводите самую большую ошибку комментариев - когда в них просто продублировано, что делает код:
# присваиваем 10 в переменную a
a = 10По вашей статье невозможно понять алгоритм, только вызубрить. Ни слова про то, что он является по сути динамическим программированием, почему он работает, что его можно делать без очереди и так будет даже быстрее на плотных графах. Вообще, правильно сначала объяснить алгоритм без очереди, а потом уже ее сверху навешивать как оптимизацию.
Можно ли узнать, лучше ли использовать по общей эффективности алгоритм A*(возможно даже bidirectional), чем просто raw Дейкстра?
Или эти вещи не стоит сравнивать?
Я до вашего комментария не читал про A*. Но теперь могу предположить, что для поиска единственного лучшего пути больше подойдет A*. Спасибо за вопрос.
Это разные классы алгоритмов. Дейкстра ищет до всех вершин, а A* до одной конкретной. A* в этом случае обычно лучше. Правда, не везде и не всегда. Если эвристика не очень точная и долго вычисляемая, то Дейкстра будет даже быстрее A*.
Вот метод, как найти все кратчайшие пути (вы в другой статье спрашивали): cначала Дейкстрой найдите расстояния до всех вершин. Потом рекурсивным перебором из конца, идите в каждую вершину, если расстояние там + длина ребра = расстоянию тут. Когда дошли до начала выводите текущий путь задом на перед. Можно, кстати, упростить этот момент, если запускать Дейкстру не из начала в конец, а наоборот, из конца в начало. Тогда восстановленый путь не надо будет разворачивать. Ну, если у вас граф не ориентированный, конечно. В ориентированном надо сначала все ребра развернуть.
Учтите только, что различных путей кратчайшей длины может быть экспоненциально много, а в случае ребер нулевой длины - вообще бесконечное количество. Кстати, для ребер отрицательной длины дейкстра вообще не работает, про это стоило упомянуть в статье.
Алгоритмы поиска путей на пальцах. Часть 2: Алгоритм Дейкстры