Distance Greater Than K

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
Intuit

Problem statement

You are given an undirected graph, a source vertex, and an integer k. Check if there is any simple path(without any cycle) from source to any vertex such that its distance is greater than 'k'.

Path in a graph is a finite or infinite sequence of edges that joins a sequence of vertices that are all distinct.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains four integers 'n', 'm', 's', and 'k' where 'n' is the number of vertices, 'm' is the no of edges, and 's' is the source vertex.

The next 'm' lines describe the edge. Each edge is characterized by three integers a, b, and c where a and b denote the endpoints of the edge and c the length of the edge.

 The edges[i][0] ,edges[i][1] contains the vertex that is connected to the edge. The edges[i][2] contains the length of edge for all 0<i<m.
Output Format : 
Return true if there is any such path otherwise false.
Note : 
Graph does not contain self-loops.
Constraints : 
1 <= 'n' <= 10
1 <= 'm' <= min(n*(n-1))/2,100)
0 <= 'a', 'b', 's' <= n-1
1 <= ci, k <= 1000000
For all 1 <= i <= m

Time Limit: 1 sec
Sample Input 1 :
6 6 0 23
0 1 5
1 2 4
2 3 5
3 4 5
4 5 5
0 5 1
Sample Output 1 :
true
Explanation For Sample Input 1 :
The graph will be :


One of the longer paths from 0 to 5 will be from the vertex 0->1->2->3->4->5.

Adding the edge weights, we get 5+4+5+5+5=24 which is greater than 23. Hence we return true.
Sample Input 2 :
4 3 1 25
0 1 1
0 2 2
2 3 3
Sample Output 2 :
false
Hint

Use backtracking from the source vertex to find all the paths.

Approaches (1)
Backtracking

The key idea will be to find all possible paths and check their path length. If the path length is greater than ‘k’ we return true. If no path has a weight greater than ‘k’ we return false.

 

The algorithm is as follows:

 

  • Create an array visited which will store whether the vertex is included in our path or not. The initial default value for all vertex will be false
  • Start from the source vertex and go through all the nodes which are connected to it and for each of them recursively try to find the longest path.
  • Keep track of the total distance. If it exceeds ‘k’ then return true.
  • Keep track of the current path vertices to make sure that it won’t be included in our path again. If it is marked as false then include it else ignore it.
  • If it does not produce distance more than ‘k’ then return false and backtrack
  • After backtracking to all the adjacent vertices marked the current vertex as unvisited such that it is removed from current path vertices.

 

From the source vertex all the paths and check if the total distance is greater than ‘k’.

Time Complexity

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

 

There are total N! paths in the graph in the worse case and checking for each path takes n time hence time complexity is O(N!) 

Space Complexity

O(N), where ‘N’ is no of vertices in the given graph. 

 

We create a visited array of size ‘N’ to keep track of vertices in the path.

Code Solution
(100% EXP penalty)
Distance Greater Than K
Full screen
Console