Graph · 35 of 43

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

Go on a hike from a start point, never visiting a spot twice, and check if some hike is at least k long.

Simple way: time O(V!)
room O(V)
Clever way: time O(V!)
room O(V)

The problem, simply

You get an undirected graph with V spots and roads that have lengths, a start spot src, and a number k. A simple path never visits the same spot twice.

Return true if some simple path starting at src has a total length of at least k. It may end at any spot.

A story to remember it

Picture it

graph

Six spots. Starting at 0, the longest simple path is 0, 1, 2, 4, 3, 5 with length 4 + 5 + 6 + 4 + 3 = 22.

looking now

Examples

The small map, k = 20

In: V = 6, edges = [[0,1,4],[1,3,2],[3,5,3],[3,4,4],[2,4,6],[1,2,5],[0,2,3]], src = 0, k = 20
Out: true

0, 1, 2, 4, 3, 5 has length 22.

A bigger map, k = 58

In: V = 9, 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]], src = 0, k = 58
Out: true

For example 0, 7, 1, 2, 8, 6, 5, 3, 4 has length 60.

The same map, k = 62

In: same edges, src = 0, k = 62
Out: false

The longest simple path from 0 is 0, 7, 1, 2, 3, 4, 5, 6, 8 with length 61. Nothing reaches 62.

k is 0

In: any graph, src = 0, k = 0
Out: true

Standing still is a path of length 0, which is already at least 0.

Way 1: the simple way

Walk every simple path from src, remember the longest total, and compare with k at the very end.

Mark src as used.
From the current spot, try every road to an unused spot. Mark it, go deeper, then unmark it when you come back.
Every time you arrive somewhere, update the longest length seen.
Return longest >= k.

java

class LongPathAll {
    static int longest;

    public static boolean hasPath(int V, int[][] edges, int src, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        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]});
        }
        longest = 0;
        boolean[] used = new boolean[V];
        used[src] = true;
        explore(src, 0, adj, used);
        return longest >= k;
    }

    static void explore(int u, int length, List<List<int[]>> adj, boolean[] used) {
        longest = Math.max(longest, length);
        for (int[] nb : adj.get(u)) {
            int v = nb[0], w = nb[1];
            if (used[v]) continue;
            used[v] = true;                              // plant the flag
            explore(v, length + w, adj, used);
            used[v] = false;                             // pull it up on the way back
        }
    }
}

How long it takes: in a crowded map the number of simple paths grows like V!, so O(V!). Extra room: the used array and a path at most V deep, O(V).

Way 2: the clever way

Nobody knows a fast way for every map. This is the longest path problem, which is NP-hard. But we can stop as soon as we have enough. That is backtracking with an early exit.

Start at src with length 0.
If the length is already at least k, return true at once. Do not look further.
Otherwise try each road to an unused spot: mark it, recurse, and if the recursion said true, pass true straight up.
If no road worked, unmark and return false.

Plant flags, back up at dead ends, stop the moment the hike is long enough

01 / 13

graph

stackcurrent path

Start at 0 with length 0. We need a path of length at least 20, never visiting a place twice.

length: 0
k: 20

looking now
answer
rejected
path
just added

java

class LongPathBacktrack {
    public static boolean hasPath(int V, int[][] edges, int src, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        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]});
        }
        boolean[] used = new boolean[V];
        used[src] = true;
        return go(src, 0, k, adj, used);
    }

    static boolean go(int u, int length, int k, List<List<int[]>> adj, boolean[] used) {
        if (length >= k) return true;                    // long enough, stop now
        for (int[] nb : adj.get(u)) {
            int v = nb[0], w = nb[1];
            if (used[v]) continue;
            used[v] = true;
            if (go(v, length + w, k, adj, used)) return true;
            used[v] = false;                             // back up and free the spot
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 4}, {1, 3, 2}, {3, 5, 3}, {3, 4, 4}, {2, 4, 6}, {1, 2, 5}, {0, 2, 3}};
        System.out.println(hasPath(6, edges, 0, 20));   // true
        System.out.println(hasPath(6, edges, 0, 23));   // false
    }
}

How long it takes: when the answer is false, every simple path is still tried, so the worst case is O(V!). When the answer is true it often stops early. Extra room: O(V) for the flags and the call stack.

Way 3: a table over sets of spots

When the worst case matters and V is at most about 20, remember results instead of re-walking. Let best[set][v] be the longest simple path that starts at src, visits exactly the spots in set, and ends at v. A set is stored as a bitmask. Build bigger sets from smaller ones by adding one road.

java

class LongPathBitmask {
    public static boolean hasPath(int V, int[][] edges, int src, int k) {
        int[][] w = new int[V][V];
        boolean[][] road = new boolean[V][V];
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            if (!road[a][b] || e[2] > w[a][b]) { w[a][b] = w[b][a] = e[2]; road[a][b] = road[b][a] = true; }
        }
        int[][] best = new int[1 << V][V];
        for (int[] row : best) Arrays.fill(row, -1);    // -1 means not possible
        best[1 << src][src] = 0;
        for (int mask = 0; mask < (1 << V); mask++) {
            for (int u = 0; u < V; u++) {
                if (best[mask][u] < 0) continue;
                if (best[mask][u] >= k) return true;
                for (int v = 0; v < V; v++) {
                    if (!road[u][v] || (mask >> v & 1) == 1) continue;
                    int next = mask | (1 << v);
                    best[next][v] = Math.max(best[next][v], best[mask][u] + w[u][v]);
                }
            }
        }
        return false;
    }
}

This takes O(2^V * V^2) time and O(2^V * V) room. For V = 20 that is about 400 million small steps, far fewer than 20!, which has 19 digits.

Watch out for

"More than k" or "at least k"? Read the statement. The classic version wants at least k, so use >=. For strictly more, use >.
Do not use plain Dijkstra or BFS and "maximize". Longest path has no shortcut like shortest path does, because going around more spots can always add length.
Lengths can be large. Use long if the sum of all roads can pass about two billion.
Mark src as used at the start, or a path may come back through it.

What interviewers ask next

Why is longest path hard but shortest path easy? Shortest paths never need loops, so best answers build on each other. For longest simple path, the "no repeats" rule makes every choice depend on the whole history.
When is longest path easy? In a graph with no cycles, like a task schedule. Process spots in topological order and take the max over incoming roads, O(V + E).
Can you prune more? Yes: if the current length plus the sum of all roads still reachable cannot reach k, stop this branch.
Hamiltonian path is the special case where every road has length 1 and k = V - 1. It is NP-complete too.

Remember this

Grown-up words: spots are vertices, trails are weighted edges, a hike without repeats is a simple path, planting and pulling flags is backtracking, the early shout is early termination, and the table over sets is bitmask dynamic programming.