Be the first user to complete this post
|Add to List|
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”
Approach: Use Depth First Search
- 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)
- Start from the source vertex and make a recursive call to all it adjacent vertices.
- During recursive call, if reach the destination vertex, increment the result (no of paths).
- See the code for more understanding.
No of paths between source: 0 and destination: 5 are: 3
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue without decrease key in O(ElogV) Hard