Question

Give an efficient algorithm that takes as input a directed acyclic graph $G=\left(V,E\right)$, and two vertices $s,t\in V$, and outputs the number of different directed paths from S to t in G.

Short answer

Depth first search algorithm is the efficient algorithm to take the directed acyclic graph as input and outputs the number of different directed paths.

Step-by-step solution

Step 1:Explain Directed Acyclic graph.

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.

Give an efficient algorithm.

Consider the directed acyclic graph $G=\left(V,E\right)$with two vertices $s,t\in 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.