# 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?

source to share

No one has answered this question yet

See similar questions:

or similar: