Last Updated: 9 Mar, 2021

Path more than distance K

Moderate

Asked in company

Solve now

Problem statement

You are given an undirected graph, a source vertex in the graph which will always be 0 (starting vertex), and a number 'K'. Your task is to find if there is a simple path, of path length greater than 'K',(without any cycle) starting from the given source vertex and ending at any other vertex. A simple path is that path in a graph that does not form a cycle.

Note:

Assume that the source vertex to always be  0.

For Example:

Here 'V' = 9, 'E' = 14 and 'K' = 60

Output: YES
Explanation: 
There exists a simple path 0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8
Which has a total distance of 61 units which is more than 60.

Input format:

The first line contains space-separated integers 'V', ’E’ and ‘K’ where ‘V’ is the number of vertices in the graph, ‘E’ the number of edges while ‘K’ denotes the sum of the weights in the simple path which should be greater than ‘K’

Then ‘E’ lines follow. Each line contains 3 space-separated integers denoting the values where the first value is vertex V1, next is vertex V2 and the last value is the weight (W) of the edge between vertices V1 and V2, respectively.

Output format:

For the given graph, set of edges, vertices, and value ‘K’, return ‘YES’ if there exists a simple path with the sum of weights greater than ‘K’ and ‘NO’ if there is no such path.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

2 ≤ V ≤ 10
1 ≤ E ≤ 20
1 ≤ K ≤ 100

Time limit: 1 second

Solve now

Approaches

01 Approach

The idea is to use Backtracking here. First, we start from the given source, explore all paths from the current vertex. We keep track of the current distance from the source. If the distance becomes more than ‘K’, we return true. If a path doesn’t produce more than ‘K’ distance, then, we backtrack.

Now the main task here is to decide that how can we make sure 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 a path, we check if it already exists or not in the current path. If it exists, we ignore the edge.

This can be implemented using the steps below:

Steps:

Take starting vertex/ source vertex as node 0, ‘SOURCE_VERTEX’.
Create another list called ‘PATH’ to keep track of all visited and unvisited vertices
Iteratively look for the valid set of paths possible from the starting ‘SOURCE_VERTEX’ until the weight becomes greater than the given ‘K’ or if an already traversed path is reached. We keep setting the respective ‘PATH’ value to True. I.e.:-
Initially, traverse the graph to get all adjacent vertices of the ‘SOURCE_VERTEX’ and recursively explore all paths from the ‘SOURCE_VERTEX’.
If the vertex is already there in ‘PATH’, then there is a cycle and we would have to ignore this edge.
If the sum of the path becomes more than ‘K’ after inclusion of that edge, return true else add this vertex to the ‘PATH’ list.
Check for all adjacent edges if they can provide a path length greater than ‘K’, If possible return True else Backtrack by removing it from ‘PATH’

4. Return ‘False’ if there are no adjacent edges that can provide a longer path length.

Solve now