Есть ли алгоритм обратный Дейкстры, который наоборот выводит самый длинный путь? Или можно ли как то изменить алгоритм Дейкстры, чтобы находил самый длинный путь?
-
1Нет. Эта задача (если имеется в виду простой путь, и граф не DAG) - NP-hard, т.е. придётся перебирать все варианты– MBoCommented 18 янв. 2022 в 18:31
-
Я так понимаю, граф ориентированный?– Qwertiy ♦Commented 18 янв. 2022 в 18:50
-
1@MBo, что-то не то. Там надо проверить ответ на бесконечность (накручиваем по циклу положительного веса) и если не бесконечность, то модифицируем веса рёбер вычитая их из максимума - на получившемся графе можно запускать дейкстру и найденный путь - ответ.– Qwertiy ♦Commented 18 янв. 2022 в 18:52
-
@Qwertiy можете поправить меня если не так? Если я правильно понимаю графы, то граф будет связной оринтеровочный, где вершины будут первая и последняя буква слов (которые будут вводить пользователь), а линии цепочка слов, Задание: написать код по мотиву игра в слова, те подается начальное слово(word) и группа слов(words) из которых будет состоять цепочка и надо составить самую длинную цепочку (По последней букве начального слова(word) выбирается следующее слово, которое на неё начинается и так далее)– nineirlCommented 18 янв. 2022 в 19:00
-
1Wiki c указанием на энпэхард в общем случае и с алгоритмом для DAG– MBoCommented 18 янв. 2022 в 19:20
|
Показать ещё 7 комментариев
1 ответ
4500й удалил ответ, но интернет помнит.
Надо добавить ещё одну проверку
- При инициализации всех вершин метки всех вершин, кроме начальной, будут равны некоторому отрицательному числу (например -1). Это нужно для того, чтобы нормально определять максимальное значение (Дейкстра работает только с положительными рёбрами);
1.5 При обходе графа вместе с весом пути хранить и сам путь.
1.6 При визите сначала проверяем, что в накопленном пути нет вершины. Если есть, то визит в данную вершину невозможен
- Далее делаем всё то же самое, что и в обычном алгоритме, но на сей раз мы изменяем значение метки следующей вершины, если оно МЕНЬШЕ суммы значения метки текущей вершины и значения ребра.
-
1Ну и, естественно, при построении плана посещений, сначала отдавать предпочтение ребрам с более высоким весом Commented 18 янв. 2022 в 18:48
-
В условии не говорится, что одну вершину можно посещать только один раз. К тому же, очень похоже, что этот алгоритм не работает даже с этой оговоркой. А после твоего комментария это кажется ещё больше.– Qwertiy ♦Commented 18 янв. 2022 в 18:58
-
Если посещать больше одного раза , то невозможно найти самый длинный по путь, потому что для любого пути
S
, всегда можно будет найти более длинный путьS'
. Пусть мы нашли некий путьS=p1,p2,p3...pN
. Его всегда можно удлинить, если посетить любые две вершины ещё разS'=p1,p2,p3,p2,p3...pN
Commented 18 янв. 2022 в 19:36 -
"К тому же, очень похоже, что этот алгоритм не работает даже с этой оговоркой" Чойта? Имелось ввиду хранить не в вершине, а в "обходе" Commented 18 янв. 2022 в 19:40
-
Его можно будет удлинить, только если в нём существуют вершины, между которыми есть цикл с положительным весом. При наличии отрицательных весов у рёбер, такой цикл вполне может не существовать даже если вообще циклы в графе есть.– Qwertiy ♦Commented 19 янв. 2022 в 0:32