91影视

A graph that has directed edges without the cycles formed is known as directed Acyclic graph. Each vertex can have more than one edge. There exists multiple paths from the source to destination.

Consider the directed acyclic graph $G=\left(V,E\right)$with two vertices $s,t鈭�V$. The number of different directed paths from S to t in G can be found by depth first search algorithm efficiently.

Procedure Graph$G\left(V,E\right)$

define Depth First Search$\left(G,u\right)$:

visited[u]=True

if $u=t$:

return 1

for v in $G\left[u\right]$:

$count+=dfs\left(G,v\right)$

return count

The above algorithm uses dfs as the procedure, to count the number of the directed path to from source to destination.

Therefore, the efficient algorithm to take the directed acyclic graph as input and outputs the number of different directed paths has been provided.