Path more than distance K

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in company
Amazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

4 3 8
0 1 5
1 2 1
2 3 1

Sample Output 1:

NO

Explanation for sample 1:

The graph corresponding to the first test case is - 


There exists no path which has a distance greater than equal to 8.

Sample Input 2:

9 14 60
0 1 4
0 7 8
1 2 8
1 7 11
2 3 7
2 5 4
2 8 2
3 4 9 
3 5 14
4 5 10
5 6 2
6 7 1
6 8 6
7 8 7

Sample Output 2:

YES
Hint

Try to use Backtracking and not BFS, DFS or picking the edge with the highest weights because a shorter edge can produce a longer path due to higher weight edges connected through it.

Approaches (1)
Graph's Traversal using backtracking

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:

 

  1. Take starting vertex/ source vertex as node 0, ‘SOURCE_VERTEX’.
  2. Create another list called ‘PATH’ to keep track of all visited and unvisited vertices
  3. 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.:- 
  4. Initially, traverse the graph to get all adjacent vertices of the ‘SOURCE_VERTEX’ and recursively explore all paths from the ‘SOURCE_VERTEX’.
  5. If the vertex is already there in ‘PATH’, then there is a cycle and we would have to ignore this edge.
  6. 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.
  7. 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.

Time Complexity

O(N!), where ‘N’ is the number of nodes (vertices) in the graph.

 

Since here, from the source node, we are visiting all the paths and checking if the total weight is greater than ‘K’ for each path. So, the worst case will be when the number of possible paths is maximum i.e. when every node is connected to every other node. So the time complexity becomes O(N!).

Space Complexity

O(N), where ‘N’ is the number of nodes (vertices) in the graph.

 

As we are using a ‘path’ list of size ‘N’ to keep track of the visited nodes so, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Path more than distance K
Full screen
Console