## Monday, May 2, 2016

### Find if there is a path of more than k length from a source - GeeksforGeeks

Find if there is a path of more than k length from a source - GeeksforGeeks
Given a graph, a source vertex in the graph and a number k, find if there is a simple path (without any cycle) starting from given source and ending at any other vertex.
`    `
`Input  : Source s = 0, k = 58  `
`Output : True  There exists a simple path 0 -> 7 -> 1  -> 2 -> 8 -> 6 -> 5 -> 3 -> 4  `
`Which has a total distance of 60 km which  is more than 58.  `

One important thing to note is, simply doing BFS or DFS and picking the longest edge at every step would not work. The reason is, a shorter edge can produce longer path due to higher weight edges connected through it.
The idea is to use Backtracking. We start from given source, explore all paths from current vertex. We keep track of current distance from source. If distance becomes more than k, we return true. If a path doesn’t produces more than k distance, we backtrack.
How do we make sure that the path is simple and we don’t loop in a cycle? The idea is to keep track of current path vertices in an array. Whenever we add a vertex to path, we check if it already exists or not in current path. If it exists, we ignore the edge.

`// This class represents a dipathted graph using`
`// adjacency list representation`
`class` `Graph`
`{`
`    ``int` `V;    ``// No. of vertices`

`    ``// In a weighted graph, we need to store vertex`
`    ``// and weight pair for every edge`
`    ``list< pair<``int``, ``int``> > *adj;`
`    ``bool` `pathMoreThanKUtil(``int` `src, ``int` `k, vector<``bool``> &path);`
};

`// Returns true if graph has path more than k length`
`bool` `Graph::pathMoreThanK(``int` `src, ``int` `k)`
`{`
`    ``// Create a path array with nothing included`
`    ``// in path`
`    ``vector<``bool``> path(V, ``false``);`

`    ``// Add source vertex to path`
`    ``path[src] = 1;`

`    ``return` `pathMoreThanKUtil(src, k, path);`
`}`

`// Prints shortest paths from src to all other vertices`
`bool` `Graph::pathMoreThanKUtil(``int` `src, ``int` `k, vector<``bool``> &path)`
`{`
`    ``// If k is 0 or negative, return true;`
`    ``if` `(k <= 0)`
`        ``return` `true``;`

`    ``// Get all adjacent vertices of source vertex src and`
`    ``// recursively explore all paths from src.`
`    ``list<iPair>::iterator i;`
`    ``for` `(i = adj[src].begin(); i != adj[src].end(); ++i)`
`    ``{`
`        ``// Get adjacent vertex and weight of edge`
`        ``int` `v = (*i).first;`
`        ``int` `w = (*i).second;`

`        ``// If vertex v is already there in path, then`
`        ``// there is a cycle (we ignore this edge)`
`        ``if` `(path[v] == ``true``)`
`            ``continue``;`

`        ``// If weight of is more than k, return true`
`        ``if` `(w >= k)`
`            ``return` `true``;`

`        ``// Else add this vertex to path`
`        ``path[v] = ``true``;`

`        ``// If this adjacent can provide a path longer`
`        ``// than k, return true.`
`        ``if` `(pathMoreThanKUtil(v, k-w, path))`
`            ``return` `true``;`

`        ``// Backtrack`
`        ``path[v] = ``false``;`
`    ``}`

`    ``// If no adjacent could produce longer path, return`
`    ``// false`
`    ``return` `false``;`
`}`

`// Allocates memory for adjacency list`
`Graph::Graph(``int` `V)`
`{`
`    ``this``->V = V;`
`    ``adj = ``new` `list<iPair> [V];`
`}`

`// Utility function to an edge (u, v) of weight w`
`void` `Graph::addEdge(``int` `u, ``int` `v, ``int` `w)`
`{`
`    ``adj[u].push_back(make_pair(v, w));`
`    ``adj[v].push_back(make_pair(u, w));`
`}`
Modify the above solution to find weight of longest path from a given source.

Read full article from Find if there is a path of more than k length from a source - GeeksforGeeks