Find if there is a path of more than k length from a source
Problem Statement
Given a weighted undirected graph, a source vertex, and a number K, determine if there exists a simple path (no repeated vertices) from the source of length at least K.
Example:
- Input:
V = 9, source = 0, K = 58, edges with weights - Output:
true(there exists a path from 0 with total weight ≥ 58)
Noob-Friendly Explanation
Imagine you're hiking and want to take a trail that's at least K kilometres long. The trails connect different viewpoints (vertices), and each trail segment has a distance (weight). You can't visit the same viewpoint twice (simple path). Can you find a hike that's long enough?
You basically try all possible hikes from the starting point, adding up distances as you go. If any hike reaches K kilometres, you're done!
Approach 1: Brute Force (DFS - Try All Paths)
Intuition
Use DFS and try all possible simple paths from the source. For each path, check if the total weight exceeds K. Since we need simple paths, mark visited vertices and backtrack.
Algorithm
- Start DFS from the source with path weight 0.
- For each unvisited neighbour, add the edge weight and recurse.
- If the accumulated weight ≥ K at any point, return true.
- Backtrack (unmark visited) to explore other paths.
import java.util.*;
public class PathMoreThanKBrute {
public static boolean hasPath(int V, List<List<int[]>> adj, int src, int K) {
boolean[] visited = new boolean[V];
visited[src] = true;
return dfs(adj, src, K, 0, visited);
}
static boolean dfs(List<List<int[]>> adj, int u, int K, int currWeight, boolean[] visited) {
if (currWeight >= K) return true;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (!visited[v]) {
visited[v] = true;
if (dfs(adj, v, K, currWeight + w, visited)) {
return true;
}
visited[v] = false; // backtrack
}
}
return false;
}
public static void main(String[] args) {
int V = 9;
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {
{0,1,4},{0,7,8},{1,2,8},{1,7,11},
{2,3,7},{2,8,2},{2,5,4},{3,4,9},
{3,5,14},{4,5,10},{5,6,2},{6,7,1},{6,8,6},{7,8,7}
};
for (int[] e : edges) {
adj.get(e[0]).add(new int[]{e[1], e[2]});
adj.get(e[1]).add(new int[]{e[0], e[2]});
}
int K = 58;
System.out.println("Path with weight >= " + K + ": " + hasPath(V, adj, 0, K));
}
}Complexity Analysis
- Time Complexity: O(V!) - in the worst case, we explore all permutations of vertices
- Space Complexity: O(V) - for the visited array and recursion stack
Approach 2: Optimal (Backtracking with Early Termination)
Intuition
This problem is NP-hard in general, so no polynomial-time solution exists. However, we can optimize the brute force with better pruning: if the current weight already exceeds K, return immediately. We can also sort adjacency lists by weight (descending) to reach K faster.
Algorithm
- Build adjacency list sorted by weight in descending order.
- Run DFS with backtracking from the source.
- Return true as soon as current path weight ≥ K (early termination).
- Prune branches where the remaining maximum possible weight can't reach K.
import java.util.*;
public class PathMoreThanKOptimal {
public static boolean hasPath(int V, List<List<int[]>> adj, int src, int K) {
// Sort adjacency lists by weight descending for faster termination
for (List<int[]> list : adj) {
list.sort((a, b) -> b[1] - a[1]);
}
boolean[] visited = new boolean[V];
visited[src] = true;
return dfs(adj, src, K, 0, visited);
}
static boolean dfs(List<List<int[]>> adj, int u, int K, int currWeight, boolean[] visited) {
// Early termination: found a valid path
if (currWeight >= K) return true;
for (int[] edge : adj.get(u)) {
int v = edge[0], w = edge[1];
if (!visited[v]) {
visited[v] = true;
if (dfs(adj, v, K, currWeight + w, visited)) {
return true;
}
visited[v] = false;
}
}
return false;
}
public static void main(String[] args) {
int V = 9;
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {
{0,1,4},{0,7,8},{1,2,8},{1,7,11},
{2,3,7},{2,8,2},{2,5,4},{3,4,9},
{3,5,14},{4,5,10},{5,6,2},{6,7,1},{6,8,6},{7,8,7}
};
for (int[] e : edges) {
adj.get(e[0]).add(new int[]{e[1], e[2]});
adj.get(e[1]).add(new int[]{e[0], e[2]});
}
int K = 58;
System.out.println("Path with weight >= " + K + ": " + hasPath(V, adj, 0, K));
}
}Complexity Analysis
- Time Complexity: O(V!) - worst case is still exponential (NP-hard problem), but pruning significantly reduces average case
- Space Complexity: O(V) - for visited array and recursion stack