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


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


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)

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of