Last Updated: 17 Feb, 2021
Distance Greater Than K
Moderate
Asked in company
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.
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
Approaches
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’.