Algorithme qui trouve le nombre de chemins simples de à dans

34

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)ststG
tstpv

poszorsvsrryyvvwzwz
Ici, DFS commencera par p , puis passera à p \ rightsquigarrow zpz 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 poryvDe 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.

Saurabh
la source
4
Notez que tous les chemins dans un graphe acyclique dirigé sont nécessairement simples (en vertu de l'acyclicité).
Noldorin

Réponses:

37

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.

dag

Le nombre de - dans un DAG est calculé par la récurrence, st

Paths(u)={1if u=t(u,v)EPaths(v)otherwise.

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)

Nicholas Mancuso
la source
J'ai compris votre algorithme et vous pouvez le rendre un peu plus efficace en utilisant la programmation dynamique car les mêmes appels récursifs sont appelés plusieurs fois, il est donc préférable de les enregistrer.
Saurabh
1
@SaurabhHota, il utilise la programmation dynamique. La première fois que le sommet est rencontré, il calcule le nombre de chemins qu’il doit . Ceci est stocké dans u.npaths. Chaque appel ultérieur à ne recalculera pas son nombre de chemins, mais simplement renverra u.npaths. utu
Nicholas Mancuso
1
Pour ces graphes, la réponse n’est-elle pas juste m ^ n où m est le nombre de nœuds d’une colonne (3 ici) et n le nombre de colonnes excluant s, t (4 ici). la sortie est 3 ^ 4 = 81 pour l'exemple de graphique.
Saadtaame
@saadtaame, bien sûr; Cependant, mon intention était simplement de présenter l'augmentation exponentielle à mesure que la "longueur" d'un graphique augmentait. Bien sûr, pour ce graphique hautement structuré, vous pouvez compter sous forme fermée, tandis que l'algorithme répertorié fonctionne pour tous les graphiques.
Nicholas Mancuso
3
Le temps d'exécution suppose que vous pouvez effectuer les ajouts nécessaires en temps constant, mais les nombres ajoutés peuvent comporter des bits dans le pire des cas. Si vous souhaitez connaître le nombre exact de chemins, le temps d'exécution (opérations de comptage de bits) est en réalité de . O(V+E)Θ(V)O(VE)
JeffE
15

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.

molyss
la source
0

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.

Vivek Anand Sampath
la source
La question demande un algorithme de temps linéaire. Votre algorithme est plus lent que cela.
DW
@Vivek pouvez-vous mentionner une référence pour les théorèmes dans votre réponse?
Hamideh