Número de rutas entre dos nodos en un DAG

Question

Quiero encontrar el número de rutas entre dos nodos en un DAG. O (V^2) y O (V + E) son aceptables.

O (V + E) me recuerda usar BFS o DFS de alguna manera, pero no sé cómo. ¿Alguien puede ayudar?

Answer 1

Realice una clasificación topológica del DAG, luego escanee los vértices del objetivo hacia atrás hasta la fuente. Para cada vértice v, lleve un recuento del número de rutas desde v hasta el destino. Cuando llegue a la fuente, el valor de ese conteo es la respuesta. Eso es O(V+E).

Answer 2

El número de rutas distintas desde el nodo u a v es la suma de distintas rutas desde los nodos x hasta v, donde x es un descendiente directo de u.

Almacene el número de rutas al nodo objetivo v para cada nodo (conjunto temporal a 0), vaya de v (aquí el valor es 1) usando orientación opuesta y recalcule este valor para cada nodo (sume el valor de todos los descendientes) hasta que llegues a ti.

Si procesa los nodos en orden topológico (nuevamente orientación opuesta), se garantiza que todos los descendientes directos ya se computaron cuando visita un nodo determinado.

Espero que ayude.