Finding all paths between multiple vertices in a DAG

For a graph G= (V, E)


  • ,
  • 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?


source to share

All Articles