Finding all paths between multiple vertices in a DAG

For a graph G= (V, E)

that:

• ,
• acyclic,
• unweighted
• may have more than one edge between two vertices (thus source and destination are not sufficient to define an edge).

And given a set of vertices, let's call them vSet

; which contains the vertex vRoot

; I need to find ALL paths pSet

between elements vSet

regarding the following:

• any vertex that appears as the source of some path in pSet
  
  must be accessible from vRoot.
• any path in pSet
  
  must have its source and destination from vSet
  
  and must not contain another vertex vSet
  
  .

I have developed an algorithm similar to BFS, which starts with vRoot

(as per 1 above), works out each of the current paths with one edge per iteration until it reaches another vertex v1

of vSet

; then save this path and start a new set of paths looking at v1

.

Here is pseudocode

output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output 
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths 
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths

      

        
        
        
      

    

Here are my questions: 1. Is this the best way to accomplish my task? 2. I tried to figure out its time complexity; I found its exponential pow (maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is it really complexity?