Hey everyone, I'm having trouble finding all paths of length < n in a graph.
I am working with a small graph at the moment to find out how to do this. Here's a
representation of it.
If I take the node Ben as my starting point, I want to return all paths with less than 5 or more nodes.
This gives :
[Ben, Steven, John]
[Ben, Steven, Mary, Jane]
[Ben, Steven, Mary, Paul]
[Ben, Chris]
[Ben, Cian, Una]
[Ben, Cian, Robert]
I don't want the paths :
[Ben, Steven, Mary, Paul, Lisa]
[Ben, Steven, Mary, Paul, Rich]
...because these have 5 or more nodes in them.
I'm a bit lost on how to do this. I've seen things like Dijkstra's Algorithm mentioned
alot when I search for help on this, but I don't really understand it for one,
and secondly it appears to find the shortest path from a node to a search point in a weighted graph, which is not quite what I want to do.
Logically, when I think about how I myself would go about doing this, I start at the root node (Ben), and follow any path. I stop when I get to a node with no children, or if n is 5. (John)
I write that down as a path and go to the last visted node where I haven't visited all the children. (Steven) I continue to follow this method for this node. When each child of the root node has been visited, I stop, because all paths have been found.
A problem I'm running into is how to go to the last visted node where I haven't visited all the children. Because my graph is single direction, a node does not know its parent node. I'm thinking perhaps every time I reach a node, I should create a stack of all its children and then pop them off as I visit. This seems like it would work better than my last idea, which was to recursively call
on everything. I managed to iterate through the graph with it, but couldn't get it to return paths successfully.
I've written a lot of text now, so I'll stop here. Hopefully somebody can point me in the right direction with regards to using a stack, how my recursive method should be written etc.