形成长度为 L 的路径的最小边数

Question

我遇到了这个问题。

给定一棵加权树 T，找到形成权重（边的权重之和）恰好为 L 的简单路径（没有重复的顶点或边）的最小边数。

---

更多详情：

L 作为输入给出，并且对于每种情况它可以不同。 树中有 N 个顶点，编号从 0 到 N - 1。

我的第一个想法是我能做的最好的事情就是遍历 T 中的所有 N^2 路径。这是带有示例输入的可运行代码。

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
    }
}

但是当N达到10,000左右时就超过了时间限制。我还考虑过对答案进行二分搜索，但检查特定答案是否可能看起来与解决原始问题一样困难。

有没有更有效的方法来解决这个问题，以某种方式避免测试所有路径？

Answer 1

考虑以下算法：

# Walk the tree in every node from Root node *Recursively (parent-weight=0):
  1 Sort the edges by Weight Descending
  2 Iterate the sorted edges in the node.
    2.1 Calculate the branch-weight: node parent-weight + edge weight
    2.2 IF branch-weight = L THEN Bingo! :)
        ELSE if branch-weight > L THEN Skip edge
        ELSE Walk the egde's end node *Recursively (parent-weight = branch-weight).

我认为这是一个相当优化的算法。