Finding all paths between multiple vertices in a DAG
For a graph
G= (V, E)
- 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
; which contains the vertex
; I need to find ALL paths
regarding the following:
- any vertex that appears as the source of some path in
must be accessible from vRoot.
- any path in
must have its source and destination from
and must not contain another vertex
I have developed an algorithm similar to BFS, which starts with
(as per 1 above), works out each of the current paths with one edge per iteration until it reaches another vertex
; then save this path and start a new set of paths looking at
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
No one has answered this question yet
See similar questions: