DSA 450 Notes

Problem Statement

Given a graph, a source vertex, and a number k, determine if there exists a simple path (without cycles) of length more than k starting from the given source.

Example:

Input:
    0 --- 1
    |     |
    |     |
    3 --- 2
    
source = 0, k = 40
Edge weights: 0-1: 10, 1-2: 10, 2-3: 10, 3-0: 40

Output: true
Explanation: Path 0 -> 1 -> 2 -> 3 has length 30, 
             Path 0 -> 3 has length 40
             But path 0 -> 1 -> 2 -> 3 -> 0 is cycle, not allowed
             
Actually: 0 -> 3 -> 2 -> 1 has length 40 + 10 + 10 = 60 > 40

Approach 1: Brute Force (Simple DFS)

Intuition

Use DFS to explore all possible paths from the source. Keep track of visited vertices to avoid cycles. If path length exceeds k at any point, return true.

Algorithm

Start DFS from source with path length 0
For each neighbor, if unvisited and edge exists, explore
Add edge weight to current length
If length > k, return true
Backtrack by unmarking visited

java

import java.util.*;

class Solution {
    public boolean dfs(List<List<int[]>> graph, int node, int k, boolean[] visited) {
        // If we've already achieved path > k
        if (k < 0) {
            return true;
        }
        
        visited[node] = true;
        
        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0];
            int weight = edge[1];
            
            if (!visited[neighbor]) {
                // Check if adding this edge gives path > k
                if (k - weight < 0) {
                    visited[node] = false;
                    return true;
                }
                
                if (dfs(graph, neighbor, k - weight, visited)) {
                    visited[node] = false;
                    return true;
                }
            }
        }
        
        visited[node] = false;  // Backtrack
        return false;
    }
    
    public boolean pathMoreThanK(List<List<int[]>> graph, int source, int k) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        return dfs(graph, source, k, visited);
    }
}

Complexity Analysis

Time Complexity: O(V × E) or O(V!) in dense graphs
Space Complexity: O(V) - Visited array and recursion stack

Approach 2: Optimal (DFS with Pruning)

Intuition

Add pruning to avoid exploring paths that cannot possibly exceed k. Calculate maximum possible remaining path length.

Algorithm

Before exploring, check if maximum possible path can exceed k
Use adjacency list for O(1) neighbor lookup
Early termination when answer found

java

import java.util.*;

class Solution {
    public boolean pathMoreThanK(List<List<int[]>> graph, int source, int k) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        return dfs(graph, source, 0, k, visited);
    }
    
    private boolean dfs(List<List<int[]>> graph, int node, int pathLen, 
                        int k, boolean[] visited) {
        // Path length exceeds k
        if (pathLen > k) {
            return true;
        }
        
        visited[node] = true;
        
        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0];
            int weight = edge[1];
            
            if (!visited[neighbor]) {
                if (dfs(graph, neighbor, pathLen + weight, k, visited)) {
                    return true;
                }
            }
        }
        
        visited[node] = false;  // Backtrack
        return false;
    }
}

Complexity Analysis

Time Complexity: O(V + E) average case with early termination
Space Complexity: O(V) - Visited array and recursion stack

Print the Path (if exists)

java

import java.util.*;

class Solution {
    public List<Integer> findPath(List<List<int[]>> graph, int source, int k) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        List<Integer> path = new ArrayList<>();
        
        if (dfs(graph, source, 0, k, visited, path)) {
            return path;
        }
        return new ArrayList<>();
    }
    
    private boolean dfs(List<List<int[]>> graph, int node, int pathLen,
                        int k, boolean[] visited, List<Integer> path) {
        path.add(node);
        
        if (pathLen > k) {
            return true;
        }
        
        visited[node] = true;
        
        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0];
            int weight = edge[1];
            
            if (!visited[neighbor]) {
                if (dfs(graph, neighbor, pathLen + weight, k, visited, path)) {
                    return true;
                }
            }
        }
        
        visited[node] = false;
        path.remove(path.size() - 1);
        return false;
    }
}

Key Takeaways

Simple Path: No vertex can be repeated in the path
Backtracking Essential: Mark visited before, unmark after exploring
Early Termination: Stop as soon as path > k is found
Weighted Graph: Track cumulative path weight
Applications: Network routing, logistics optimization
NP-Complete Related: Longest path problem is NP-complete

Find if there is a path of more than k length from a source

Problem Statement

Approach 1: Brute Force (Simple DFS)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (DFS with Pruning)

Intuition

Algorithm

Complexity Analysis

Print the Path (if exists)

Key Takeaways