i have always been curious on how this particular problem is best solved. The closes thing i could find to my problematic was the pipeline game concept,see screenshot
i have a grid of 10x10. every rectangle of the grid can connect to the adjacent fields with 1 to 4 edges (no diagonals, just top,bot,left,right) on the left side of the grid there can be 10 starting points, one on each row, and on the right 10 end points also 1 in each row of the grid.
Now my question: what is the most efficient way to find all the possible paths from the starting point to any of the end points and also all the dead-end paths (the path that has a couple of points connected to the starting point but doesn't connect to any of the end points)?
I have tried the breadth-first search algorithm to find all the paths between them, but is there any better alternatives i could try out?
Usually A* is much faster then BFS, for finding shortest path on a graph.
A* requires you to have an admissible heuristic function [the manhattan distance heuristic can usually be applied on a grid], and is usually much faster then BFS, since it is informed - so it preferes investigating nodes which are more likely to lead to a better solution.
Note that A* is also complete [finds a path if there is one] and also optimal [finds the shortes path].
EDIT:
A* also allows more trade off of time/performance: for example: By using a weighted A*, you will get a non-optimal solution, but you are likely to get it much faster.
Note that for uninformed A* [h=0] by invoking A* you get a dijkstra, which is exactly BFS for non-weighted edges
