Graph – Print all paths between source and destination
Objective: Given a graph, source vertex and destination vertex. Write an algorithm to print all possible paths between source and destination.
This problem also known as “Print all paths between two nodes”
Approach: Use Depth First Search
- Start from the source vertex and visit the next vertex (use adjacency list).
- Now if you look carefully, the new problem is to find paths from the current vertex to destination. For instance as per the example above, start from vertex 0 and visit vertex 1. Now all the paths from vertex 1 to vertex 5 will be included in our final result if we add vertex 0. So make a recursive call with source as vertex 1 and destination as vertex 5.
- Keep track of visited nodes to avoid cycles.
- Add current vertex to result (taking string here) to keep track of path from source.
- Once reach to the destination vertex, print the path.
- Now visit the next node in adjacency list in step 1 and repeat all the steps (loop)
- See the code for more understanding.
->0->1->2->3->4->5 ->0->1->3->4->5 ->0->2->3->4->5
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.