Каким образом лучше выполнять поиск всех возможных путей в ориентированном графе?

Имеется ориентированный граф.
Каждое ребро графа имеет вес (условно обозначу #). Задача - найти все возможные пути из вершины 1 к выходу. При этом учитывается только прохождение рёбер с весами.
При первом прохождении ребра, вес становится нулевым, после чего выполняется поиск новых доступных путей. Таким образом, имеется некоторое множество свободно доступных вершин (А) и множество рёбер с весами, связанных с этими вершинами.

Граф планирую обходить рекурсивно с возвратом убранных весов при возвращении.

Звучит просто: прошел ребро - добавь связанные с новой вершиной рёбра. Но вся проблема в том, что возможна ситуация, как на рисунке. После прохождения ребра 6-7, доступны будут только рёбра 7-8 и 7-9. А затем, после прохождения пути 7-9-5 мы вернёмся к ранее пройденным вершинам и придётся из обходить.

Альтернативы, пришедшие в голову:
1. Держать в памяти множество пройденных вершин и, отдельно, список множеств вершин, доступ к которым был отрезан. Но не уверен, насколько сложно будет это совместить с рекурсивным обходом с возвратом.
2. Объединять все свободно взаимосвязанные вершины в одну с привязыванием к ней всех доступных рёбер. Опять же, возврат звучит проблемно.

Скорее всего, в обоих случаях придётся передавать весь граф в качестве аргумента.

Дополнительные сведения:
- Вершин планируется около 20-30.
- Рёбер немного больше.

0

Забыл приложить схему.

Миниатюры

 

0