Алгоритм алгоритма выполнения для поиска пути от узла к корню в ориентированном графе

Question

У меня есть ориентированный граф со специальным корневым узлом, из которого доступны все остальные узлы.

Весьма легко найти произвольный алгоритм для поиска всех патчей с узла-получателя до корня, например solution (DFS) using LinkedHashSets.

Ну, этот алгоритм хорошо работает для небольших графиков, но с большими графиками он не подходит к концу в разумные сроки.

Мой примерный граф имеет 129 узлов и 200 ребер. В моих глазах неОГРОМНЫЙ экстремально граф ...

Может кто-нибудь дать мне подсказку, как эффективно решить эту проблему?

Возможно, мы сможем использовать другие свойства моих графиков. Все они:

• подключен
• направлен с петлями
• имеет назначенный начальный узел
• имеет Назначенный конечный узел

Answer 1

Ну, не на самом деле - вы не можете сделать это значительно более потому что сам размер вывода огромен. Количество путей экспоненциальная числа узлов, взгляните на этом простом примере:

V = {a, b, c}, E = {(a,b), (a,c), (b,c)} 

Это выглядит довольно просто, есть «только» 2 доли не имеет тривиальные пути в графе, ведущей к с. a-> c, a-> b-> c.

Теперь рассмотрим добавление узла d с ребрами (д, а), (d, б) - вы будете иметь 3 пути ведущие к c от нового корня, d->a->b->c, d->a->c, d->b->c, до сих пор не так уж плохо, но обратите внимание, что происходит при добавлении e с (e,d),(e,a), вы получите одно «семейство» путей, начиная с e->d (3 над дорожками) и, кроме того, «семейство» путей, начинающихся с «e-> a» (2 пути). всего 5 путей. Повторяя этот процесс, вы получите еще два семейства, один с 5 путями, а другой с тремя путями. Вероятно, вы начинаете понимать, что если вы повторите процесс k раз, вы получите #fibo(k) разные пути, but the fibonacci number is very, very big for inputs such as 100 (~ 354 * 10^20, и быстро растет).

Таким образом, что бы вы ни делали - поиск всех путей на графике будет неэффективным, за исключением некоторых «простых» графиков, таких как деревья.

---

ТЛ; др:
Есть экспоненциальное число путей, ведущих к вашему целевому узлу, и найти все из них занимает экспоненциальное время. DFS - это надежное решение этой проблемы.