# 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)
2. for each edge e that destination of p is its source
ii. else
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?

+2

source to share

All Articles