CODEWITHSUNDEEP
algorithmgraph-algorithm
konsolas
konsolas

Reputation: 1091

Identifying paths between nodes on a graph, whilst finding potential loops

Lets say I have a graph like the following: graph

It is directed, and can also have cycles. If I wanted to find all the possible routes from node 0 to node 9, I have found that I could use a depth-first search algorithm, keeping the list of visited nodes in a collection to prevent the cycles from affecting the algorithm.

However, what I haven't been able to work out is how I can adapt DFS to find which nodes could be passed more than once when travelling between node 0 and node 9.

In the example, we can see that nodes 1, 5, 6, and 3 could be accessed more than once if travelling from 0 to 9, due to the loops. However, I'm not sure how this can be effectively implemented in an algorithm.

I have already tried counting the number of times a node is visited, but this seems to cause the algorithm to iterate infinitely.

How can I find all possible paths between two points in a directed graph, whilst simultaneously finding the points that could be accessed more than once (in a loop) on the way?

Upvotes: 2

Views: 202

Answers (1)

kraskevich
kraskevich

Reputation: 18566

You can do it separately in linear time.

Let's find strongly connected components and shrink them. Now we've got a DAG.

A node can be passed twice (or more times) iff the size of the component is greater than 2, it's reachable from the source node, and the target node is reachable from it.

If you're fine with exponential time, you can use the following fact: if there a path that contains the given node twice, there is such a path with at most 3n vertices (let's take a look at its two occurrences. We can cut out all cycle between them. We can also cut out all cycle before and after them).

That is, you can keep using your recursive solution (which never terminates), but always kill a branch of recursion if you've got more than 3n nodes in the path (there might be an even better bound than 3n, but this one is easy to prove).

Upvotes: 2

Related Questions