How to do the Number of Paths Algorithm

Video Lesson: The Number of Paths Algorithm

How to do the Number of Paths Algorithm

To do the Number of Paths Algorithm:

1. Decide on the two directions of travel from start to finish.
2. From the start node, write 1s at each outer node in the two directions of travel.
3. At each inner node, add the two numbers that enter into this node in the direction of travel.
4. Repeat the process until the final node is reached.
5. The number written at the final node is the number of paths.

The following examples consider the number of paths algorithm on grids with no restrictions. That is, all edges of the network can be moved along and all nodes can be visited. There are no obstacles.

Number of Paths on a Grid: Example 1

The number of paths algorithm will be conducted on a 2×3 grid.

Step 1. Decide on the directions of travel

The directions of travel in the number of paths algorithm are the directions to the finish node from the starting node.

In the example below, the finish node is upwards and to the right of the starting node.

Therefore, the directions of travel in this example are upwards and rightwards.

The number of paths algorithm only considers direct paths. If any paths involved going downwards or leftwards, the paths would be looping back on themselves and would not be direct paths.

Two examples of paths are shown above. However, there are more paths that can be found and to ensure we have found them all, the number of paths algorithm is used.

Step 2. From the start node, write 1s at the outer nodes in the two directions of travel

The 2 directions of travel in this example are upwards and rightwards.

From the start node, we write a 1 at each node in the upwards and rightwards direction as shown below.

This is because from the start node there is only one way to get to any of these nodes.

Since we are not allowed to travel left or down, the only way to get to these nodes is by going directly up or directly right.

We do not put any 1s on the other outside edges as there is more than one way to get to these nodes and this will be calculated in the algorithm.

Step 3. At each inner node, add the two numbers that enter into this node in the direction of travel

For example at the node below we add 1+1 to make 2, which is written at the node.

We added the 1 from the left and the 1 from below.

This means that there are 2 paths to get to this node: either right then up or up then right.

Step 4. Repeat this process until the finish node is reached

Moving upwards and rightwards to get to each new node, the two numbers from below and to the left of each node are added together.

Step 5. The number written at the final node is the number of paths

Finally, 6+4=10 is written at the final node.

Therefore, there are 10 different paths from start to finish.

Number of Paths on a Grid: Example 2

Find the number of paths from start to finish in the grid below.

Step 1. Decide on the directions of travel

The finish node is downwards and rightwards of the starting node and so, the directions of travel are downwards and rightwards.

Step 2. From the start node, write 1s at the outer nodes in the two directions of travel

We put 1s on the nodes directly to the right of the start and directly below the start.

Step 3. At each inner node, add the two numbers that enter into this node in the direction of travel

The completed number of paths algorithm is shown below. There are 15 different paths through the grid from start to finish.

The Number of Paths Algorithm with Restrictions

The number of paths algorithm can be used on networks with restrictions or obstacles. To find the number of paths from start to finish that avoid a particular node, first set the value of this node equal to zero and then complete the number of paths algorithm as usual.

For example, the following grid has the restriction in which the number of paths must be found that go from start to finish but do not pass through node X.

Place a zero at any nodes in which the paths cannot pass through.

The first step is to put a zero at node X. This is because we do not want any paths to pass through this point.

Complete the number of paths algorithm as usual

Now the number of paths algorithm is completed as usual.

We are travelling upwards and rightwards, so 1s are placed at the outer edges upwards and rightwards of the starting node.

Now to find the sums at each internal node by adding the numbers that come in from below and from the left.

There are 9 paths from start to finish that avoid the node X.

The Number of Paths Algorithm Passing Through a Point

To find the number of paths that pass through a node:

1. Decide on the directions of travel from start to finish.
2. Put zeros at any node that involve going against these directions from the node that must be passed through.
3. Complete the number of paths algorithm, adding the values at any nodes that go in the directions of travel.

From start to finish in the network below, we must travel upwards and rightwards.

Therefore we put zeros at any node that involves going from node X and then left or down.

The image below shows zeros placed at nodes that involve going left after passing through node X.

Now the following zeros are also written in at nodes that involve going down from node X.

Now the number of paths algorithm is completed by writing 1s at the other nodes that go on the outer edges from the start upwards or rightwards as shown.

Now the inner nodes are calculated by adding the numbers that come in from below or from the left.

We can see that there are 10 paths in total from start to finish that must pass through node X.

The zeros are used to block any unwanted paths.