Архив форумов ЦИТФорума

[GY-GY]

Имеетя некий граф. Надо найти все возможные маршруты для попадания из одной произвольной вершины в другую, исключая закольцованные участки.
с алгоритмами нахождения кратчайшего пути(Дейкстры) - знаком, но мне нужны все варианты, исключая те, где одну вершину посешаем более 1 раза. Может есть решение и не надо изобретать велосипед?

[slop]

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

Posted with ForumPilot v1.1

[GY-GY]

[Odomontois]

Вам нужны сами маршруты или их количество?
Хотя погодите,,, если рекурсивно - это поиск в глубину, вам не нужно никаких массивов - только одну единственную рассматриваемую трассу, если вам нужно их генерировать.
А если нужно не только генерировать, но и хранить, то меньшими объёмами не обойтись.