Find the path between given vertices in a directed graph

Given a directed graph and two vertices (say source and destination vertex), determine if the destination vertex is reachable from the source vertex or not. If the path exists from the source vertex to the destination vertex, print it.


 

For example, there exists two paths {0-3-4-6-7} and {0-3-5-6-7} from vertex 0 to vertex 7 in the following graph. Whereas there is no path from vertex 7 to any other vertex.

Directed graph

 
We can use Breadth First Search (BFS) algorithm to efficiently check the connectivity between any two vertices in the graph. The idea is to start the BFS routine from the source vertex and check if the destination vertex is reached during the traversal. If the destination vertex is not encountered at any point, we can say that it is not reachable from the source vertex.

 

Download   Run Code

Output:

Path exists from vertex 0 to vertex 7

 

How to print the complete path?

The idea is to store the complete path between the source and destination vertex in a vector or an array using recursion. This can be easily achieved if Depth First Search (DFS) is used to determine path between the vertices. This is demonstrated below in C++:

 

Download   Run Code

Output:

Path exists from vertex 0 to vertex 7
The complete path is: 0 3 4 6 7

 
The time complexity of above solutions is O(n + m) where n is number of vertices and m is number of edges in the graph.

 
Exercise: Extend the solution to print all paths between given vertices (solution link)

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of