277. Graph – Count all paths between source and destination

Objective: Given a graph, source vertex and destination vertex. Write an algorithm to count all possible paths between source and destination.

Condition: Graph does not contain any cycle.

This problem also known as “paths between two nodes”

Example:

Approach: Use Depth First Search

1. Use DFS but we cannot use visited [] to keep track of visited vertices since we need to explore all the paths. visited [] is used avoid going into cycles during iteration. (That is why we have a condition in this problem that graph does not contain cycle)
2. Start from the source vertex and make a recursive call to all it adjacent vertices.
3. During recursive call, if reach the destination vertex, increment the result (no of paths).
4. See the code for more understanding.

Output:

No of paths between source: 0 and destination: 5 are: 3

Related Problems:

- Optimizing Test Execution: Managing Test Dependencies for Sequential Order Medium
- Articulation Points OR Cut Vertices in a Graph Hard
- Graph – Find Cycle in Undirected Graph using Disjoint Set (Union-Find) Hard
- Graph – Print all paths between source and destination Medium
- Given Graph - Remove a vertex and all edges connect to the vertex Medium