Algoritmo que encuentra el número de caminos sencillos de a en

Puede alguien me sugieren un algoritmo de tiempo lineal que toma como entrada una dirigido acíclico gráfico y dos vértices y y devuelve el número de caminos sencillos de a en . Tengo un algoritmo en el que ejecutaré un DFS (Profund First Search) pero si DFS encuentra entonces no cambiará el color (de blanco a gris) de ninguno de los nodos que vienen en la ruta para que si esta es la subruta de cualquier otra ruta, entonces DFS también vuelve a pasar por esta subruta. Por ejemplo, considere la lista de adyacencia donde necesitamos encontrar el número de rutas de p a v .$G=(V,E)$$s$$t$$s$$t$$G$
$t$$s \rightsquigarrow t$$p$$v$

$$\begin{array}{|c|c c c|} \hline p &o &s &z \\ \hline o &r &s &v\\ \hline s &r \\ \hline r &y \\ \hline y &v \\ \hline v &w \\ \hline z & \\ \hline w &z \\ \hline \end{array}$$ Aquí DFS comenzará con $p$ y luego digamos que va a $p \rightsquigarrow z$ ya que no encuentra $v$ DFS se ejecutará normalmente. la ruta es $psryv$ ya que se encuentra con $v$ , no cambiaremos el color de los vértices $s,r,y,v$ a gris. Luego la ruta $pov$ ya que el color de $v$ todavía es blanco. Luego la ruta $posryv$ ya que el color de $s$ es blanco y de manera similar camino $poryv$También se mantiene un contador que se incrementa cuando se encuentra $v$ .

¿Es correcto mi algoritmo? si no, qué modificaciones son necesarias para corregirlo o cualquier otro enfoque será muy apreciado.

Nota : Aquí he considerado el algoritmo DFS que se proporciona en el libro "Introducción a los algoritmos de Cormen" en el que colorea los nodos de acuerdo con su estado. Por lo tanto, si el nodo no es visitado, inexplorado y explorado, entonces el color será blanco, gris y negro respectivamente. Todas las demás cosas son estándar.

Su implementación actual calculará el número correcto de rutas en un DAG. Sin embargo, al no marcar rutas, tomará un tiempo exponencial. Por ejemplo, en la siguiente ilustración, cada etapa del DAG aumenta el número total de rutas en un múltiplo de 3. Este crecimiento exponencial se puede manejar con programación dinámica.

El cálculo de la cantidad de rutas - en un DAG viene dado por la recurrencia, $s$$t$

$$\text{Paths}(u) = \begin{cases} 1 & \text{if } u = t \\ \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\ \end{cases}$$

Una modificación simple de DFS calculará esto dado como

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

No es difícil ver que cada borde se mira solo una vez, por lo tanto, un tiempo de ejecución de .$O(V + E)$

Solo necesita notar que la cantidad de rutas desde un nodo al nodo objetivo es la suma de la cantidad de rutas desde sus elementos secundarios hasta el objetivo. Sabes que este algoritmo siempre se detendrá porque tu gráfico no tiene ningún ciclo.

Ahora, si guarda el número de rutas de un nodo al objetivo mientras visita los nodos, la complejidad del tiempo se vuelve lineal en el número de vértices y la memoria lineal en el número de nodos.

El número de caminos entre dos vértices en un DAG se puede encontrar usando la representación de matriz de adyacencia.

Suponga que A es la matriz de adyacencia de G. Tomando el poder Kth de A después de agregarle la matriz de identidad, le da el número de caminos de longitud <= K.

Dado que la longitud máxima de cualquier ruta simple en un DAG es | V | -1, calcular | V | -1ª potencia daría una cantidad de rutas entre todos los pares de vértices.

El cálculo de | V | -1 th poder se puede hacer haciendo log (| V | -1) multiplicaciones cada uno de TC: | V | ^ 2.