Homework Help

Number of distinct paths: How many possible routes can one take to get from point A to...

user profile pic

utilityfan | Student, College Freshman | Valedictorian

Posted June 6, 2012 at 4:34 AM via web

dislike 2 like

Number of distinct paths: How many possible routes can one take to get from point A to point B?

 

How many possible routes can one take to get from point A to point B?

http://img713.imageshack.us/img713/796/boxei.png

2 Answers | Add Yours

user profile pic

txmedteach | High School Teacher | (Level 3) Associate Educator

Posted June 6, 2012 at 6:07 AM (Answer #1)

dislike 1 like

We need to start by putting parameters on what a "possible route" is. If we just leave it as it is without changing the original question, then the number of paths will be infinite!

If you don't constrain the direction you are allowed to travel, but you do say there are no cycles, then the problem can't be solved in any clever way. You, or your computer, must trace each possible path and keep a tally.

The most systematic method to do this problem is found if we only allow movement between nodes to the right or into the page. In other words, we can easily find a solution without brute force if each path taken must close the distance between your pencil and point B.

The easiest way to do this problem is to make what's called an "adjacency matrix," which is a square matrix ` ` where N is the number of vertices, and each element of the matrix is derived as follows: `a_(ij)=1` if node `i` has an edge leading to `j`, and `a_(ij)=0` if node `i` does not have an edge leading to `j`.

In our case, we'll start by first labeling each node with a number by starting at the top left on the face towards us and proceeding right, then wrapping back to the left in the middle row, then to the bottom row, then doing the same for the back side. 

The front face will look like `[[1,2,3],[4,5,6],[7,8,9]]` , and the back face (viewed from the front) will look like `[[10,11,12],[13,14,15],[16,17,18]]`.

This gives us an adjacency matrix of the following when you consider the connections given in the picture:

`A = [[0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]`

We may have frontloaded some of the work involved in doing this problem by bothering to make this matrix, but it will soon pay off. Adjacency matrices have the spectacular property that in order to determine the number of possible paths of length n, we do the following calculation:

`p_n = A^n`

Here, `p_n` is the number of paths of length `n`. To find the total possible number of paths between two points, `i` and `j`, we would need to perform the following calculation:

`p_n(i,j) = sum_(k=1)^oo A^n(i,j)`

Here, `A^n(i,j)` is the element of `A^n` in row `i`, column `j`. You can see from this relation that if we did not put constraints on the graph like we did, we would have an infinite number of paths, or we would have no way to ensure we never came back to the same node!

For us, the only time the number of possible paths is nonzero is found when we have the 5th power of `A`. In other words (remember, point A is node 1, and point B is node 18):

`p_n(1,18) = sum_(k=1)^oo A^n(1,18) = A^5(1,18)`

To calculate `A^5(1,18)`, we simply perform matrix multiplication to find the final result. There are 30 possible paths from A to B.


Again, if you can't put these constraints on the problem, unfortunately, there is no nice way to do it; you need to draw out every path, yourself!

Sources:

user profile pic

mlehuzzah | Student , Graduate | (Level 1) Associate Educator

Posted June 6, 2012 at 12:18 PM (Answer #2)

dislike 1 like

I'm assuming that each path must take you closer to B (for example: no tracing an outline of a square seven times and then going to B). Then there are a finite number of paths and here is a way to find them:


Every path from A to B requires you to move to the right twice, to move down twice, and to move "back" (into the screen) once. You don't have to do these moves in this order, but you do have to do them.

Call these moves RRDDB (right, right, down, down, back).

The number of paths is the number of ways to rearrange these letters. For example, each of the following represents a path from A to B:
BRDRD, DDRBR, RDBRD, etc

The number of ways to rearrange a "word" is:

(number of letters in the word)! / (number of copies of a duplicate letter)!

So for us it is: 5!/(2!2!) = 120/(2*2)=30

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes