Оптимальное решение для: всех возможных ациклических путей в задаче графа

Question

Я имею дело с неориентированным графом.Мне нужно найти все возможные ациклические пути в графе:

with G(V,E)
find all subsets of V that are acyclic paths

Я использую Python Scipy или Matlab - в зависимости от того, что будет уместно.Есть ли какое-нибудь умное решение для этого?

Я пытаюсь добиться этого с помощью поиска в ширину (см. Вики)

У меня также есть этот набор инструментов в matlab: http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolbox но, похоже, нет простого решения моей проблемы.

PS.Практически проблема сформулирована следующим образом: Проблема проектирования транзитной сети: Найти такую ​​транспортную сеть, которая сводит к минимуму стоимость пассажиров и операторов (т. Е. Оптимальная сеть метро для городских районов)

Заранее спасибо Rafal

Answer 1

Я думаю, что проблема, указанная в вашем PS, может быть проблемой NP. Если так, то есть прямые решения только для графов с очень ограниченным числом узлов (N ~ <= 20). Другие решения будут приблизительными, что приведет к появлению только локальных оптимумов. Решение вашей проблемы, как указано в вопросе, будет просто для расчета всех перестановок порядков узлов. Опять же, это станет невозможным в вычислительном отношении при сравнительно небольшом количестве узлов (возможно, выше 20, но не намного). </p>

Answer 2

Вам нужны только кратчайшие пути между всеми парами вершин или действительно все пути?