LINUX.ORG.RU
Форум — Development  

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

 


0

1

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

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



Последнее исправление: jcdr (всего исправлений: 3)
← Как выделить подстроку в SED (получить то, что входит в паттерн)
Сравнить два фрагмента текста и выделить разницу →

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

Pershin ★
()

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

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

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

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

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

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

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

jcdr
() автор топика

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

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

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

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

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

jcdr
() автор топика

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

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

pathfinder ★★★★
()

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

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

MKuznetsov ★★★★★
()

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

Aswed ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Как выделить подстроку в SED (получить то, что входит в паттерн)
Development
Сравнить два фрагмента текста и выделить разницу →