Algorithme qui trouve le nombre de chemins simples de à dans

Quelqu'un peut - il me suggérer un algorithme linéaire qui prend en entrée un graphe orienté acyclique et deux sommets et et retourne le nombre de chemins simples de à dans . J'ai un algorithme dans lequel je vais lancer un DFS (recherche approfondie d'abord) mais si DFS trouve il ne changera pas la couleur (du blanc au gris) des nœuds qui dans le chemin sorte que si c'est le sous-chemin d'un autre chemin, alors DFS le répète également. Par exemple, considérons la liste de contiguïté où nous devons trouver le nombre de chemins de p à 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}$$ Ici, DFS commencera par $p$ , puis passera à p \ rightsquigarrow z$p \rightsquigarrow z$ puisqu'il ne rencontrera pas $v$ DFS fonctionnera normalement. Maintenant chemin est $psryv$ puisqu'il rencontre $v$ nous ne changerons pas la couleur des sommets $s,r,y,v$ en gris.Alors le chemin $pov$ puisque la couleur de $v$ est toujours blanc.Alors le chemin $posryv$ puisque la couleur de $s$ est blanc et pareillement de chemin $poryv$De plus, un compteur est maintenu qui est incrémenté lorsque $v$ est rencontré.

Mon algorithme est-il correct? sinon, quelles modifications sont nécessaires pour le corriger ou toute autre approche sera grandement appréciée.

Remarque : Ici, j'ai considéré l'algorithme DFS qui est donné dans le livre "Introduction aux algorithmes de Cormen" dans lequel il colore les nœuds en fonction de son statut. Ainsi, si le nœud est non visité, non exploré et exploré, sa couleur sera blanche, gris et noir respectivement.Toutes les autres choses sont standard.

Votre implémentation actuelle calculera le nombre correct de chemins dans un DAG. Cependant, en ne marquant pas les chemins, cela prendra un temps exponentiel. Par exemple, dans l'illustration ci-dessous, chaque étape du DAG augmente le nombre total de chemins d'un multiple de 3. Cette croissance exponentielle peut être gérée avec une programmation dynamique.

Le nombre de - dans un DAG est calculé par la récurrence, $s$$t$

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

Une simple modification de DFS calculera cette donnée comme

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

Il n’est pas difficile de voir que chaque bord est regardé une seule fois, d’où un temps d’exécution de .$O(V + E)$

Vous devez seulement noter que le nombre de chemins d'un nœud au nœud cible est la somme du nombre de chemins de ses enfants à la cible. Vous savez que cet algorithme va toujours s'arrêter car votre graphique n'a pas de cycles.

Désormais, si vous enregistrez le nombre de chemins d'un nœud à la cible lors de la visite des nœuds, la complexité temporelle devient linéaire en nombre de sommets et la mémoire en linéaire en nombre de nœuds.

Le nombre de chemins entre deux sommets quelconques dans un DAG peut être trouvé à l'aide de la représentation de la matrice d'adjacence.

Supposons que A soit la matrice d'adjacence de G. Prendre la Kth de la puissance de A après y avoir ajouté la matrice d'identité donne le nombre de chemins de longueur <= K.

Puisque la longueur maximale de tout chemin simple dans un DAG est | V | -1, le calcul de la puissance de | V | -1 donnerait le nombre de chemins entre toutes les paires de sommets.

Calculer | V | -1 ème puissance peut être fait en effectuant log (| V | -1) muliplications chacune de TC: | V | ^ 2.