CODEWITHSUNDEEP
graph-theorygraph-algorithm
Keysersoze
Keysersoze

Reputation: 194

Find paths between two sets of nodes

I have a graph. I want to get every possible paths between a source node and a target node.

I'm looking for a performant algorithm because I will have to do that for two sets of nodes (sources and targets)

Let's take an example. my graph

Given this graph, I want to get every possible paths between :

The result should be :

Upvotes: 1

Views: 167

Answers (1)

Codor
Codor

Reputation: 17605

Enumeration of all paths between two nodes can be solved by using depth-first search. However, a few points should be taken in consideration.

  1. If the input graph is permitted to contain cycles and repetition of nodes in the path is permitted, there might be infinitely many paths between a ginven pair of nodes.

  2. Even if repetition of nodes is not allowed the number of paths between a given pair of nodes might grow exponentially in the number of nodes in the input; hence, it is necessary to clarify what is to be understood as a 'performant' algorithm, as the usual polynomially bounded runtime complexity does not qualify - the output may grow exponentially in the size of the input.

Upvotes: 1

Related Questions