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.

#define N 5

int graph[N][N] = {
{0,1,1,0,1},
{0,0,0,0,0},
{0,1,0,1,0},
{0,0,0,0,0},
{0,0,1,1,0},};

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.

#include<iostream>
#include<string.h>
using namespace std;

#define N 5

int graph[N][N] = {
{0,1,1,0,1},
{0,0,0,0,0},
{0,1,0,1,0},
{0,0,0,0,0},
{0,0,1,1,0},};

int visited[N];
int maximum = 0;

void findmaxPath(int src, int dest, int c) {

	visited[src] = true;

	if (src == dest) {
		if (maximum < c)
			maximum = c;
	}

	for (int i = 0; i < N; i++) {
		if (visited[i] == false && graph[src][i])
			findmaxPath(i, dest, c + 1);
	}
	// back track
	visited[src] = false;
}

int main() {
	// set all nodes unvisited
	memset(visited, 0, sizeof(visited));
	findmaxPath(0, 3, 0);
	cout << maximum << endl;

	return 0;
}

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



Related Contents to follow