Given a graph
G= (V, E) that is:
- may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).
And given a set of vertices, let's call them
vSet; that contains a vertex
vRoot; I need to find ALL paths
vSet elements respecting the following:
- any vertex that appears as a source for some path in
pSetmust be reachable from vRoot.
- any path in
pSetmust has its source and destination from
vSet, and must not contain any other vertex of
I've developed an algorithm similar to BFS, that starts from
vRoot (according to 1 above), grow each of the current paths with one edge per an iteration until it reaches another vertex
vSet; then store this reaching path and start growing new set of paths staring from
Here is a pseudo code
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 achieve my task? 2. I was trying to figure out its time complexity; I found that its exponential of pow(maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is this really the complexity?