Nombre de chemins entre deux nœuds dans un DAG

Je veux trouver le nombre de chemins entre deux nœuds dans un DAG. O(V^2) et O(V+E) sont acceptables.

O(V+E) me rappelle d'une certaine façon utiliser BFS ou DFS, mais je ne sais pas comment.
Quelqu'un peut-il aider?

Est-ce devoirs?
Cela devrait migrer vers la théorie

OriginalL'auteur Saiiiira | 2011-03-02

  1. 20

    Faire un tri topologique de la DAG, puis analyser les sommets de la cible vers l'arrière à la source. Pour chaque sommet v, tenir le compte du nombre de chemins de v à la cible. Lorsque vous arrivez à la source, la valeur de comptage est la réponse. C'est O(V+E).

    OriginalL'auteur Jeremiah Willcock

  2. 6

    Le nombre de voies distinctes de nœud u vers v est la somme des chemins différents à partir des nœuds x de v, où x est un descendant direct de u.

    Stocker le nombre de chemins d'accès à la cible nœud v pour chaque nœud (temporaire mis à 0), à partir de v (ici, la valeur est 1) à l'aide de à l'opposé de l'orientation et de recalculer cette valeur pour chaque nœud (somme de la valeur de tous les descendants) jusqu'à ce que vous atteignez u.

    Si vous traitez les nœuds dans l'ordre topologique (encore une fois en face de l'orientation) vous avez la garantie que tous les descendants directs sont déjà calculés lorsque vous visitez nœud donné.

    Espère que cela aide.

    OriginalL'auteur stalker