algorithm - 寻找长路径

Question

我有一个包含 1000000 个节点的稀疏未加权有向图，我想找到所有长度为 5 的简单路径。我知道长度为 5 的简单路径很少(可能只有一条)。

我从 http://en.wikipedia.org/wiki/Longest_path_problem 看到确定图是否具有长度为 k 的路径的参数化复杂度为 O(2^k n poly(n,k)))，尽管我不知道这些方法是否也能解决我的问题。不幸的是，我发现的所有方法看起来都非常复杂，而且似乎没有实现。

有人可以用或多或少简单的语言解释一个我可以实现的快速解决方案吗？

Answer 1

我写了一个 implementation of the Color-Coding method对于最长路径。然而，它只用大约 10000 个顶点的图进行了测试；此外，它可能无法找到所有大小为 5 的路径(它旨在找到一小组有趣的路径)。我也许可以根据您的目的对其进行调整，如果您有兴趣，请给我留言。

编辑:颜色编码的思想是用 5 种颜色随机为图形的顶点着色。希望我们正在寻找的路径的 5 个顶点都收到不同的颜色。如果这是真的，我们可以用动态规划找到它。当然，概率只有0.0384；但是如果我们重复整个过程，例如500 次，我们错过它的机会只有 3*10^-9 左右。这只是基本方案，还有很多技巧可以加快速度。