Re: find all directed paths between a source and destination

On Apr 9, 11:00 pm, Ginu <osheik...@xxxxxxxxx> wrote:
Hello all. I have a graph (that is not necessarily directed) of a
number of nodes. I'm trying to enumerate through all directed paths
between source and destination (to avoid routing loops). There
shouldn't be an infinite number of solutions to this problem because
nodes cannot be traversed more than once in the solution. Has anybody
come across a solution for this? Thanks in advance.

The trivial solution would be to simply iterate over all paths
starting at the source, s, i.e. pick the first edge of s, (s,v), try
all possible paths from v to the destination, t, without going through
s, choose the next edge of s, try all possible paths ..., and so on.
No path will be enumerated twice. You could preprocess the graph with
e.g. a DFS, removing all vertices such that they are either not
reachable from s or cannot reach the destination, t, as well as
contracting edges between pairs of degree-two vertices. This way, you
should be able to prove a, in a sense optimal, Theta(E + k)-complexity
in a uniform-cost RAM with k being the number of enumerated paths.
Perhaps the space complexity, O(V log V), can be significantly
improved.
.

Relevant Pages