# Find the number of paths between two points on a grid **URL:** \ **Category:** random\ **Created:** [April 5, 2006, 2:02am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425 "2006-04-05T02:02:00Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![oessmartkid](https://avatars.discourse-cdn.com/v4/letter/o/97f17d/32.png) [@oessmartkid](https://forum.kirupa.com/u/oessmartkid)\ **Post date:** [April 5, 2006, 2:02am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/1 "2006-04-05T02:02:00Z")
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. ---
**Author:** ![SlowRoasted](https://avatars.discourse-cdn.com/v4/letter/s/a698b9/32.png) [@SlowRoasted](https://forum.kirupa.com/u/SlowRoasted)\ **Post date:** [April 5, 2006, 2:13am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/2 "2006-04-05T02:13:12Z")
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? ---
**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\ **Post date:** [April 5, 2006, 2:20am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/3 "2006-04-05T02:20:48Z")
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. ---
**Author:** ![krilnon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/krilnon/32/34_2.png) [@krilnon](https://forum.kirupa.com/u/krilnon)\ **Post date:** [April 5, 2006, 2:27am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/4 "2006-04-05T02:27:46Z")
Nokrev probably meant this: [http://www.kirupa.com/developer/actionscript/depth\_breadth\_search.htm](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. ---
**Author:** ![JoshuaJonah](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/joshuajonah/32/1775_2.png) [@JoshuaJonah](https://forum.kirupa.com/u/JoshuaJonah)\ **Post date:** [April 5, 2006, 2:47am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/5 "2006-04-05T02:47:24Z")
> [@Krilnon](#): > > Nokrev probably meant this: [http://www.kirupa.com/developer/actionscript/depth\_breadth\_search.htm](http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm) actually, i believe he meant this: [http://www.kirupa.com/developer/actionscript/abstract\_data\_types.htm](http://www.kirupa.com/developer/actionscript/abstract_data_types.htm) ---
**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\ **Post date:** [April 5, 2006, 2:50am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/6 "2006-04-05T02:50:49Z")
Aye, Defective is right. Thanks 🙂 ---
**Author:** ![JoshuaJonah](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/joshuajonah/32/1775_2.png) [@JoshuaJonah](https://forum.kirupa.com/u/JoshuaJonah)\ **Post date:** [April 5, 2006, 2:52am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/7 "2006-04-05T02:52:32Z")
np:beam: ---
**Author:** ![oessmartkid](https://avatars.discourse-cdn.com/v4/letter/o/97f17d/32.png) [@oessmartkid](https://forum.kirupa.com/u/oessmartkid)\ **Post date:** [April 5, 2006, 3:11am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/8 "2006-04-05T03:11:54Z")
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). ---
**Author:** ![MTsoul](https://avatars.discourse-cdn.com/v4/letter/m/91b2a8/32.png) [@MTsoul](https://forum.kirupa.com/u/MTsoul)\ **Post date:** [April 5, 2006, 3:38am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/9 "2006-04-05T03:38:13Z")
I see what you mean. This is a math probability problem right? Let me draw you a diagram. ![](http://img143.imageshack.us/img143/6154/cci000022ze.png) 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. ---
**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\ **Post date:** [April 5, 2006, 4:03am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/10 "2006-04-05T04:03:44Z")
Well… not quite infinite, but very, very many. :lol: ---
**Author:** ![oessmartkid](https://avatars.discourse-cdn.com/v4/letter/o/97f17d/32.png) [@oessmartkid](https://forum.kirupa.com/u/oessmartkid)\ **Post date:** [April 5, 2006, 4:31am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/11 "2006-04-05T04:31:58Z")
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. ---
**Author:** ![krilnon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/krilnon/32/34_2.png) [@krilnon](https://forum.kirupa.com/u/krilnon)\ **Post date:** [April 5, 2006, 11:18am UTC](https://forum.kirupa.com/t/find-the-number-of-paths-between-two-points-on-a-grid/184425/12 "2006-04-05T11:18:23Z")
> [@Defective](#): > > actually, i believe he meant this: > [http://www.kirupa.com/developer/actionscript/abstract\_data\_types.htm](http://www.kirupa.com/developer/actionscript/abstract_data_types.htm) Yeah, that’s the one I was thinking about originally, but then I ran into the other and changed my mind.