Code for identifying roads on squares
Hi all,
I am trying to code up something like this: I have a square with 1 point on each edge (1,2,3,4). I want to list all possibilities to reach from 1 to 4 like 1,2,3,4
and 1,3,2,4. There might be more than one squares and points, and I always go from a point to another. For example, I have two merged squares, and therefore there exists 6 edges and 6 points. I want to go from 1 to 6, now. My possible ways are 1,2,3,6; 1,4,5,6; 1,2,5,6; and so on. Is there an algorithm or an easy way to do this on c++? I will use this as an input to another code.
Thanks.
I am trying to code up something like this: I have a square with 1 point on each edge (1,2,3,4). I want to list all possibilities to reach from 1 to 4 like 1,2,3,4
and 1,3,2,4. There might be more than one squares and points, and I always go from a point to another. For example, I have two merged squares, and therefore there exists 6 edges and 6 points. I want to go from 1 to 6, now. My possible ways are 1,2,3,6; 1,4,5,6; 1,2,5,6; and so on. Is there an algorithm or an easy way to do this on c++? I will use this as an input to another code.
Thanks.
Pathfinding algorithms. A* is a common one:
http://en.wikipedia.org/wiki/A_star
http://en.wikipedia.org/wiki/A_star#Pseudocode
http://en.wikipedia.org/wiki/A_star#Example
http://en.wikipedia.org/wiki/A_star
http://en.wikipedia.org/wiki/A_star#Pseudocode
http://en.wikipedia.org/wiki/A_star#Example
> I want to list all possibilities
In general, that is not worthwhile. ¿what's the final goal?
Also, I don't understand your example paths
In general, that is not worthwhile. ¿what's the final goal?
Also, I don't understand your example paths
Ok, I am sorry, I will explain more clearly. I have two squares that are merged. So, we have 6 points and edges. Points 1,2,3 are at the top and 4,5,6 are at the bottom. Thus, I can go from 1 to 6 through the path 1,2,3,6 or 1,4,5,6 or 1,2,5,6, and so on. Is it more clear now?
I was referring to your first example
If you've got just one square 1,2 on the top and 3,4 on the bottom
then the paths are (1,2,4) and (1,3,4)
However, I insist that find all the paths is a waste of time.
Consider http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics (monotonic paths), and that's with strong restrictions.
If you still want to do it, use a search algorithm like dfs or bfs. When you reach the goal, store the path and backtrace.
If you've got just one square 1,2 on the top and 3,4 on the bottom
then the paths are (1,2,4) and (1,3,4)
However, I insist that find all the paths is a waste of time.
Consider http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics (monotonic paths), and that's with strong restrictions.
If you still want to do it, use a search algorithm like dfs or bfs. When you reach the goal, store the path and backtrace.
Actually I need to print all the paths between two nodes. It is an undirected graph. The edges are 1-2, 1-3, 2-4, 3-4. I should find the paths between node 1 and 4. I will have roughly 50 of the nodes, so I need an efficient algorithm. Is there a sample code to use?
Topic archived. No new replies allowed.