Given a set of ordered pairs that represent the nodes of a graph, determine the number of paths that exist between two nodes. Note that each node may be visited just once in each path. A path is defined here as a vertical or horizontal move from one node to an adjacent node. How would I go about solving this problem.
Im guessing you are supposed to find a formula to apply to the problem right? If you gotta find an actual answer we don’t have enough info. How many rows and columns? What are the two points on the graph?
There was some tutorial Kirupa was working on a while back that would find the shortest path between any two points… I just can’t find it at the moment. Search the tutorials.
Nokrev probably meant this: http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm
A path is defined here as a vertical or horizontal move from one node to an adjacent node.
I don’t like this sentence. To be adjacent nodes(vertices), your two nodes would have to be directly connected to eachother in order to form what you’re defining to be a path.
Normally a line connecting two vertices is an edge, and if those two vertices share at least one edge, they are adjacent vertices. Also, I’m assuming that you mean ‘coordinate plane’, not ‘graph’. If you meant the sort of graph that is used in graph theory, vertical or horizontal movement wouldn’t be an issue.
actually, i believe he meant this:
http://www.kirupa.com/developer/actionscript/abstract_data_types.htm
Aye, Defective is right. Thanks 
np:beam:
Well this is a programming venture so I, these are some more accure descriptions, I start out with a 5x5 grid. In that 5x5 grid certain nodes are given, then an initial point and end point are given. The goal is to find the total number of paths (path cannot repeat, and needs to be horizontal and vertical movements).
I see what you mean. This is a math probability problem right?
Let me draw you a diagram.
So basically have 1’s on all the TOP and LEFT sides. Then each of the other corners is just the sum of its adjacent left and adjacent top numbers, as shown in the pic. And you can do this with complex grids as well, ones that aren’t square
Oh and this is asuming you can only go right and down. Otherwise, you’d have infinite paths.
Well… not quite infinite, but very, very many. :lol:
thanks for all of your help. I am thinking about using depth-first searching and go from the root or origin point and try every possiblity until it leads me to the end point.
Yeah, that’s the one I was thinking about originally, but then I ran into the other and changed my mind.
