Найти все пути в ориентированном невзвешанном графе с циклами

[Pr0[)!9Y]

Собственно сабж. Гуглил, но гуглить по неизвестному материалу сложновато. Везде предлагается найти кратчайший или n кратчайших. В моем случае нужно найти все пути от одной вершины к другой. Всё осложняется присутствием циклов в графе.
Заранее спасибо.

Добавлено 27.07.10, 15:18
Производительность посредственна.

[OpenGL]

А ничего, что таких путей может быть бесконечное число - я могу миллион раз прокрутиться по циклу и только потом пройти дальше

[vk]

Значит, нужно записать множество всех путей в общем виде, примерно как мы пишем решение неопределенной системы уравнений. Встретил цикл, обозначь числом k произвольное количество проходов по нему и иди дальше.

[esperanto]

это не достаточно, а потом путей может быть несчетное множество

[Pr0[)!9Y]

Ммм, ну я же вот и говорю, что не знаком с материалом. Как бы объяснить.
Мне нужны все различные пути между двумя вершинами, где каждое ребро в конкретном пути встречается только единожды.

[esperanto]

тогда можне решить полным перебором, на все возможные пермутации ребер

[Pr0[)!9Y]

Ссылку на материал какой-нибудь, или хотя бы определение на словах "возможные пермутации ребер" можно?

[esperanto]

Пусть есть три ребра 1 2 3

Тогда все пермутации это
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1

Т.е все разные порядки на ребрах

[Pr0[)!9Y]

А потом выбросить те наборы, которые не начинаются с нужной вершины и не заканчиваются нужной, а также те которые не смежны (если так называется два ребра с одной вершиной) или не совпадает направление?

Я думал можно это выбрасывать на этапе перестановок как-то.

[esperanto]

Цитата Pr0[)!9Y @ 27.07.10, 20:07

А потом выбросить те наборы, которые не начинаются с нужной вершины и не заканчиваются нужной, а также те которые не смежны (если так называется два ребра с одной вершиной) или не совпадает направление?

Я думал можно это выбрасывать на этапе перестановок как-то.

Да.

ДА.

[OpenGL]

Цитата Pr0[)!9Y @ 27.07.10, 18:38

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

Это понимать как "любое ребро встречается ровно один раз" или "любое ребро встречается максимум один раз"?

[Pr0[)!9Y]

Цитата OpenGL @ 28.07.10, 03:43

максимум

[OpenGL]

Тогда перестановки не работают, т.к. могут существовать пути, не содержащие каких-либо определенных вершин. Да к тому же при числе ребер, превышающих 20, программа будет работать слишком долго, даже с условием о некритичности времени Можно предложить вариант перебора, отсекающий все ненужные пути:

1. Кладем в очередь начальную вершину. Каждая вершина содержит список путей в виде последовательности ребер, ведущих из начальной вершины в данную, и флагов "просмотра" данного пути (по ходу объяснения станет ясно, зачем они нужны). В начальную вершину записывается единственный путь, содержащий пустой список ребер и флаг, что не просматривали.
2. Достаем из очереди вершину.
3. Для каждого ребра, ведущего из данной вершины:
   
   1. Добавляем все непросмотренные пути текущей вершины, в которых нет рассматриваемого ребра, в вершину, куда ведет это ребро.
      
   2. Добавляем ко всем добавленным путям рассматриваемое ребро и помечаем их все непросмотренными.
      
   3. Кладем ту вершину в очередь.
4. Помечаем все пути текущей вершины просмотренными.
5. Если очередь не пуста, идем к п.2.

В конце мы получим в конечной вершине список путей, ведущих в нее. Единственное НО - алгоритм не будет работать в случае петель (то есть когда ребро выходит и входит в одну и ту же вершину), но легко адаптируется под этот случай.

[Pr0[)!9Y]

Цитата OpenGL @ 28.07.10, 10:08

Тогда перестановки не работают, т.к. могут существовать пути, не содержащие каких-либо определенных вершин.

Да, понял я это когда реализовал несколько алгоритмов найденных в сети. И т.к. я рекурсию исключил, из-за большой ее глубины, модифицировать например 4-й листинг отсюда чтобы добавлялись пути не из всех вершин после мучений так и не удалось. Всё увенчалось тем, что я не оценил насколько долго это будет работать.

OpenGL, огромное спасибо. Всё получилось. Только маленькая деталь, без которой у меня выходил вечный цикл. Добавлять вершину в очередь надо только в том случае, если был добавлен хотя бы один путь.

[esperanto]

Цитата OpenGL @ 28.07.10, 10:08

Тогда перестановки не работают,

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


Алгоритм экспоненциальный, Ваш алгоритм тоже экспоненциальный. Экспоненциальные алгоритмы медленые. Но полиномианльного не существует.