0

Есть ли алгоритм обратный Дейкстры, который наоборот выводит самый длинный путь? Или можно ли как то изменить алгоритм Дейкстры, чтобы находил самый длинный путь?

12
  • 1
    Нет. Эта задача (если имеется в виду простой путь, и граф не DAG) - NP-hard, т.е. придётся перебирать все варианты
    – MBo
    Commented 18 янв. 2022 в 18:31
  • Я так понимаю, граф ориентированный?
    – Qwertiy
    Commented 18 янв. 2022 в 18:50
  • 1
    @MBo, что-то не то. Там надо проверить ответ на бесконечность (накручиваем по циклу положительного веса) и если не бесконечность, то модифицируем веса рёбер вычитая их из максимума - на получившемся графе можно запускать дейкстру и найденный путь - ответ.
    – Qwertiy
    Commented 18 янв. 2022 в 18:52
  • @Qwertiy можете поправить меня если не так? Если я правильно понимаю графы, то граф будет связной оринтеровочный, где вершины будут первая и последняя буква слов (которые будут вводить пользователь), а линии цепочка слов, Задание: написать код по мотиву игра в слова, те подается начальное слово(word) и группа слов(words) из которых будет состоять цепочка и надо составить самую длинную цепочку (По последней букве начального слова(word) выбирается следующее слово, которое на неё начинается и так далее)
    – nineirl
    Commented 18 янв. 2022 в 19:00
  • 1
    Wiki c указанием на энпэхард в общем случае и с алгоритмом для DAG
    – MBo
    Commented 18 янв. 2022 в 19:20

1 ответ 1

1

4500й удалил ответ, но интернет помнит.

Надо добавить ещё одну проверку

  1. При инициализации всех вершин метки всех вершин, кроме начальной, будут равны некоторому отрицательному числу (например -1). Это нужно для того, чтобы нормально определять максимальное значение (Дейкстра работает только с положительными рёбрами);

1.5 При обходе графа вместе с весом пути хранить и сам путь.

1.6 При визите сначала проверяем, что в накопленном пути нет вершины. Если есть, то визит в данную вершину невозможен

  1. Далее делаем всё то же самое, что и в обычном алгоритме, но на сей раз мы изменяем значение метки следующей вершины, если оно МЕНЬШЕ суммы значения метки текущей вершины и значения ребра.
5
  • 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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.