I am working on a recursive DFS to retrieve all paths between two nodes in an undirected and unweighted graph for now. It takes the start and end node, and DFS on the node and its adjacent nodes recursively while saving the paths. I was wondering whether there is a more efficient way to find all paths?
4
votes
If you want to find all the paths, then you have to walk through all of them... Do you just want to find the number of paths? Then there may be faster methods.
- irrelephant
If you are interested only in the number, though, there might be more efficient algorithms
- Boris Strandjev
@irrelephant I want to do some work on the nodes on each of these paths; thus I need to find all the paths and save them, not just their number.
- Fatima
2 Answers
3
votes
There are exponential number of simple paths, and DFS is basically creating all of them 0 so your approach is correct, though time consuming (but this is a part of the problem itself, not the algorithm).
You might be able to optimize it a bit by eliminating from the graph nodes that do not lead to the target, if such nodes exist - effectively trimming unsuccesful searches before calculating them.
Be aware that if the graph contain cycles - there could be infinite number of paths (though finite number of simple paths). Note that to avoid an infinite loop and get all simple paths, your DFS will need to maintain a visited set, that is modified per path (once "discovering" a node insert it to set, and once it is popped from the stack, remove it from the set).
1
votes
You can adapt Dijkstra's algorithm, also see A Recursive Algorithm to Find all Paths Between Two Given Nodes
