Для заданного графа G(V, E), исходной вершины s и конечной вершины d проблема состоит в том, чтобы найти все возможные пути из < em>s до d, где G может содержать петли и циклы. Я хочу получить все простые пути, цикл не разрешен.
Какова будет сложность этой задачи?
Эта задача является NP-сложной, поскольку ее выходные данные могут иметь экспоненциальный размер по сравнению с ее входными данными.
Поиск самого длинного пути между двумя точками уже является NP-трудным (сведение к задаче о гамильтоновом пути), так что найти их все также.
Вы также можете увидеть, что эта задача имеет экспоненциальную сложность, увидев, что может быть экспоненциальное число путей между двумя вершинами в графе.
Вот небольшой пример:
Пусть G будет графом с 3n+2 вершинами. Пусть V = {s,d} U {a1, ..., an} U {b1, ..., bn} U {c1, ..., cn} будет его набором вершин. Ребра строим следующим образом:
-от s до a1
- для i in 1...n строим ребро из ai to bi, из ai to ci
- для i in 1..n-1 строим ребро из bi to ai+1, из ci to ai+1.
- из bn to d, из cn to d.
Как видите, существует около 2^n путей из s в d.
