Distance Greater Than K
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
Output Format : Return true if there is any such path otherwise false. Note : Graph does not contain self-loops. Constraints : 1

Question

Distance Greater Than K

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



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

Accepted Answer

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’.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(n!)Explanation:

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!)

Python (3.5)

'''

    Time Complexity  : O(N!)

    Space Complexity : O(N)

  

    Where N is no of vertices.



'''

from collections import defaultdict



def distancegreaterthanKHelper(graph, currentVertex, k, visited, dist = 0):

	

    # If dist greater than k return true

	if (dist > k):

		return True

	visited[currentVertex] = True

	

    # Traversing over adjacent vertices

	for i in graph[currentVertex]:

		if (visited[i[0]] == True):

			continue



		# adding the edge distance in the recursion call

		ch = distancegreaterthanKHelper(graph, i[0], k, visited, i[1] + dist)

		if (ch==1):

			return True



	# Removing current vertex from path

	visited[currentVertex] = False

	return False



def distancegreaterthanK(edges, n, s, k, m):

    

	visited=[False]*(n + 1)

	graph=[[] for i in range(n+1)]

 

	# Converting the edges into adjacency list

	for i in range(m):

		graph[edges[i][0]].append((edges[i][1], edges[i][2]))

		graph[edges[i][1]].append((edges[i][0], edges[i][2]))

	return distancegreaterthanKHelper(graph, s, k, visited)

C++ (g++ 5.4)

/*

    Time Complexity  : O(N!)

    Space Complexity : O(N)

  

    Where N is no of vertices.



*/

bool distancegreaterthanKHelper(vector>>&graph, int currentVertex, int k, vector&visited, int dist = 0)

{

	// If dist greater than k return true

	if (dist > k)

	{

		return true;

	}

	visited[currentVertex] = true;

	

    // Traversing over adjacent vertices

	for (auto i : graph[currentVertex])

	{

		if (visited[i.first] == true)

		{

			continue;

		}



		//  adding the edge distance in the recursion call

		bool ch = distancegreaterthanKHelper(graph, i.first, k, visited, i.second + dist);

		if (ch)

		{

			return true;

		}

	}



	// Removing current vertex from path

	visited[currentVertex] = false;

	return false;

}

bool distancegreaterthanK(vector>&edges, int  n, int s, int k, int m)  

{

	vectorvisited(n + 1, false);

	vector  >>graph(n + 1) ;

	

    // Converting the edges into adjacency list

	for (int i = 0; i < m; i++)

	{

		graph[edges[i][0]].push_back({edges[i][1], edges[i][2]});

		graph[edges[i][1]].push_back({edges[i][0], edges[i][2]});

	}

	return distancegreaterthanKHelper(graph, s, k, visited);

}

Java (SE 1.8)

/*

    Time Complexity  : O(N!)

    Space Complexity : O(N)

  

    Where 'N' is no of vertices.

*/



import java.util.Arrays;

import java.util.ArrayList;



public class Solution

{

    public static boolean distancegreaterthanKHelper(ArrayList>> graph, int currentVertex, int k, boolean[] visited, int dist)

    {

        // If dist greater than k return true

        if (dist > k)

        {

            return true;

        }

        visited[currentVertex] = true;



        // Traversing over adjacent vertices

        for (int i = 0; i < graph.get(currentVertex).size(); i++)

        {

            if (visited[graph.get(currentVertex).get(i).get(0)] == false)

            {

                boolean ch = distancegreaterthanKHelper(graph, graph.get(currentVertex).get(i).get(0), k, visited, graph.get(currentVertex).get(i).get(1) + dist);

                if (ch == true)

                {

                    return true;

                }

            }

        }



        // Removing current vertex from path

        visited[currentVertex] = false;

        return false;

    }



    public static boolean distancegreaterthanK(ArrayList> edges, int n, int s, int k, int m)

    {

        boolean[] visited = new boolean[n + 1];

        Arrays.fill(visited, false);



        // Create Adjacency List.

        ArrayList>> graph = new ArrayList>>();



        for (int i = 0; i < n; i++)

        {

            graph.add(new ArrayList>());

        }



        for (int i = 0; i < edges.size(); i++)

        {

            ArrayList temp = new ArrayList();

            temp.add(edges.get(i).get(1));

            temp.add(edges.get(i).get(2));

            graph.get(edges.get(i).get(0)).add(temp);

           

            ArrayList temp2 = new ArrayList();

            temp2.add(edges.get(i).get(0));

            temp2.add(edges.get(i).get(2));

            graph.get(edges.get(i).get(1)).add(temp2);

        }



        return distancegreaterthanKHelper(graph, s, k, visited, 0);

    }

}

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 :

Output Format :

Note :

Constraints :

Top TCS Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in TCS Software Developer