Given a directed graph and two vertices ( source and destination ),  find maximum path to reach from source to destination. For example in the below directed graph if the source vertex is 0 and destination vertex is 3, the maximum path would be 3 ( 0-4-2-3).

find maximum path to reach from source to destinationfind maximum path to reach from source to destination using backtracking

In the above directed graph a path is an edge. For example there are three routes to reach at vertex 3 from vertex 0. 

  1. 0-2-3  [ path count 2]
  2. 0-4-3  [ path count 2]
  3. 0-4-2-3 [path count 3]

So , our answer would be 3.

Solution:

Use adjacency matrix to represent the above directed graph. Following is the adjacency matrix.

Start exploring all paths from source vertex to destination and update the maximum count of paths. If there is no solution path found backtrack to the previous vertex and explore the path again until the destination vertex found. Look at the below solution.

Note: The backtracking method for single source shortest path problem is not a better option in terms of time complexity. Use Dijkstra algorithm for single source shortest path problem.

Ref:

https://en.wikipedia.org/wiki/Backtracking