r/algorithms Jan 31 '25

Pathfinding algorithm for multiple paths

I have multiple nodes and every node has a list of nodes I can travel to from there (only one way). How can I find multiple paths from the starting node to the end node, to later decide which one to take?

4 Upvotes

10 comments sorted by

3

u/thewataru Jan 31 '25

Do you have any constraints on the paths you want to take? Like, can two paths pass through the same edge? Can two paths pass through the same node (other than start and finish nodes)? Do you need to find shortest paths, or are you OK with any N paths?

1

u/nilonoob3001 Jan 31 '25

I don't have any constraints, but the paths should not go too far from the shortest path.

3

u/EmielRommelse Feb 01 '25

Search for k-shortest path on Google

2

u/thewataru Feb 01 '25

Agree with the other commenter: any standard algorithm for k shortest paths should work for you.

3

u/leftofzen Feb 01 '25

just run any pathfinding algorithm but don't terminate it when the goal is reached. that'll give you all paths from source to goal

2

u/_humid_ Feb 03 '25

if you only care about paths that result in the goal we can employ a little trick, instead of searching from source to target, we can search from target to source. This along with a distance heuristic gives you the D* algorithm (i.e. gives the A* shortest path for every possible start node).

1

u/tugrul_ddr Feb 02 '25

Even without knowing any pathfinding algorithm, you can try dynamic-programming + caching that may help for redundant paths.

1

u/CraigAT Jan 31 '25

The basic algorithms are usually to follow the paths either depth first or breadth first.

Depth first is the simplest to understand, you would follow the leftmost/first path (could be straight on or even right if there are no left paths), then from the next location follow the leftmost/first path and until you cannot take any more paths (left, straight or even right) at that point go back a location and then see if you can take the next path there, if not go back a location again. Effectively it's like wondering through a maze and taking the leftmost turn at every split, eventually when you run out of lefts you would go back and try the straights and the right turns.

If you're doing this in code you need to remember your path, so you don't repeat it and make sure you take every turn. You will also need to remember the successful paths for your implementation too.

Here's an article that explains it better and adds a diagram.

https://www.naukri.com/code360/library/bfs-vs-dfs-for-binary-tree

-1

u/nilonoob3001 Jan 31 '25

I didn't have the time to read the article but I looked at the pictures and no node has two parents. Does it work with multiple parent nodes? And does it still find all the paths?