Number of Paths Algorithm: Step-by-Step Guide
The number of paths algorithm is a method to calculate the number of possible paths between two points on a grid, considering specific movement directions. This guide provides detailed steps and examples to help you understand and apply this algorithm effectively.
Example 1: Counting Paths Between A and E

Output: There are 4 paths connecting A and E.
Explanation: The paths connecting A to E are as follows:
- Directly from A to E.
- From A through B, and then to E.
- From A through C, and then to E.
- From A through B, then D, then C, and finally to E.
Example 2: Counting Paths Between A and C
Output: There are 2 paths connecting A and C.
Explanation: The paths connecting A to C are as follows:
- Directly from A to C.
- From A through B, then D, and finally to C.
Steps to Use the Number of Paths Algorithm
- Decide on Directions of Travel: Choose the two directions allowed (e.g., right and up).
- Mark 1s at Outer Nodes: Starting from the start node, write 1s at each node in the chosen directions.
- Add Numbers at Inner Nodes: At each inner node, sum the numbers from the two directions.
- Repeat Until Final Node: Continue this process until reaching the final node.
- Read the Number at the Final Node: This number represents the total number of paths.
Example: 2×3 Grid
- Directions: Upwards and rightwards.
- Initial Marking:
- Place 1s at nodes directly upwards and rightwards from the start.
- Inner Node Calculation:
- Add numbers entering each inner node.
- Final Node: The number at the final node gives the total paths.
Example: For a 2×3 grid, there are 10 different paths from start to finish.
Counting Paths Between Two Vertices Using Backtracking
To solve this problem, the approach of backtracking is used. The idea is to explore all potential paths starting from the source vertex and check if they lead to the destination. If a path reaches the destination, it is counted as a valid path. If not, the path is discarded, and the algorithm backtracks to explore other options. This method of exploring the graph is known as backtracking.

Explanation of Backtracking:
- Backtracking Process: Start from the source vertex and attempt different paths.
- If a path reaches the destination, count it as a valid path.
- If the path fails to reach the destination, discard it and backtrack to explore another path.
In the graph example, there are four paths connecting vertex A (source) and vertex E (destination).
Why This Approach Fails with Cycles:
If the graph contains cycles, this approach may run indefinitely. For instance, if there is an additional edge between vertices C and B, it forms a cycle (B -> D -> C -> B). In such a case, the path length continues to increase as the cycle repeats, resulting in an infinite number of paths.

Steps to Solve the Problem:
- Create a Recursive Function:
- This function accepts the index of the current node and the destination node.
- Use a global or static variable to keep track of the number of valid paths.
- Track Visited Nodes:
- Use an array to mark nodes as visited during traversal.
- When backtracking, reset the node’s status to unvisited to explore other paths.
- Check for Destination:
- If the current node matches the destination, increment the path count.
- Explore Adjacent Nodes:
- For each node connected to the current node, call the recursive function again with the next node’s index and the destination.
- Output the Total Count:
- Print the total count of valid paths as the final result.
Handling Restrictions
To avoid specific nodes, set the value of these nodes to zero and complete the algorithm as usual.
Example: On a grid with a restricted node X, set the value of X to zero and calculate paths normally. This ensures paths do not pass through X.
Passing Through a Specific Point
To find paths passing through a specific node, modify the algorithm:
- Set zeros at nodes requiring backward travel from the specific node.
- Calculate the number of paths as usual.
Example: For paths passing through node X, place zeros at nodes requiring left or downward travel from X and complete the algorithm.
Conclusion:
The number of paths algorithm is a systematic method to determine all possible paths between two points on a grid. By following the steps and handling restrictions correctly, you can accurately calculate paths for various grid configurations.