Question
Minimum edges to form path with length L
I came across this problem.
Given a weighted tree T, find the minimum number of edges to form a simple path (no duplicate vertices or edges) of weight (sum of weights of edges) exactly L.
More details:
L is given as input and it can be different for each case. There are N vertices in the tree numbered from 0 to N - 1.
My first thought was the best I can do is go over all the N^2 paths in T. Here is a runnable code with example input.
import java.util.*;
class Edge {
int toVertex, weight;
Edge(int v, int w) {
toVertex = v; weight = w;
}
}
class Solver {
// method called with the tree T given as adjacency list and the path length L to achieve
// method to return minimum edges to create path of length L or -1 if impossible
public static int solve(List<List<Edge>> T, long L) {
int min = (int) 1e9;
for (int i = 0; i < T.size(); i++) {
min = Math.min(min, test(T, L, i, -1, 0, 0));
}
if (min == (int) 1e9) {
return -1;
} else {
return min;
}
}
static int test(List<List<Edge>> T, long L, int vertex, int parent, long length, int edges) {
if (length == L) {
return edges;
} else if (length < L) {
int min = (int) 1e9;
for (Edge edge : T.get(vertex)) {
if (edge.toVertex != parent) {
min = Math.min(min, test(T, L, edge.toVertex, vertex, length + edge.weight, edges + 1));
}
}
return min;
} else {
return (int) 1e9; // overshoot
}
}
}
// provided code
public class Main {
static void putEdge(List<List<Edge>> T, int vertex1, int vertex2, int weight) {
T.get(vertex1).add(new Edge(vertex2, weight));
T.get(vertex2).add(new Edge(vertex1, weight));
}
public static void main(String[] args) {
// example input
List<List<Edge>> T = new ArrayList<List<Edge>>();
int N = 8;
for (int i = 0; i < N; i++) T.add(new ArrayList<Edge>());
putEdge(T, 0, 1, 2);
putEdge(T, 1, 2, 1);
putEdge(T, 1, 3, 2);
putEdge(T, 2, 6, 1);
putEdge(T, 6, 7, 1);
putEdge(T, 3, 4, 1);
putEdge(T, 3, 5, 4);
System.out.println(Solver.solve(T, 5L)); // path from 4 to 5 have 2 edges and length 5
}
}
But this exceeds time limit when N reaches around 10,000. I also considered binary search on the answer, but checking a particular answer is possible looks just as hard as solving the original problem.
Is there a more efficient way to solve this to somehow avoid testing all paths?