LINUX.ORG.RU

поиск путей на графе

 


0

1

Есть такая задача. Граф (вершины, ребра). Цикличный, невзвешенный, ненаправленный. Надо найти все возможные пути между двумя произвольно выбранными вершинами (не только кратчайший). Подскажите, есть ли известный (а точнее - как называется) эффективный алгоритм для такой задачи?

(В пути не должно быть повторного прохода по вершинам)


Эффективный - это смотря с чем сравнивать. Время тут в любом случае будет экспоненциальным. Если под неэффектичным понимать поиск в ширину - кстати, вы его пробовали делать? - то может что-то и есть, только здесь вряд ли подскажут.

Pershin ()

былоб это так просто с «эффективный алгоритм», не извращались бы с коммивояжерами.

anonymous ()
Ответ на: комментарий от Pershin

Ну «эффективный» - относительное понятие. Как найти путь поиском в ширину - я понимаю. Я не понимаю пока - как правильно при поиске очередного пути не повторять уже найденные ранее.

jcdr ()
Ответ на: комментарий от jcdr

кажется, можно использовать префиксное дерево для проверки наличия такого пути. тогда примерно как делать

jcdr ()

Если в тупую, перебираешь все подграфы, ищешь кратчайший путь в каждом, ?????, PROFIT, но экспоненциальненько выходит

anonymous ()
Ответ на: комментарий от xaizek

слишком много возвратов в этом случае будет. Но теперь картинка того, как делать, сложилась - спасибо

jcdr ()

Надо найти все возможные пути

Их может быть бесконечное число. Должны быть ещё ограничения, например ни одну вершину нельзя посещать дважды.

pathfinder ★★★★ ()

В гугол! Н. Кристофидес: Теория графов. Алгоритмический подход ; 1978г

обратить внимание на год издания..

MKuznetsov ★★★★★ ()

А в чем собственно сама задача? Может есть более простое решение чем искать все пути в цикличном ненаправленном графе?

Aswed ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.