1

I have a sparse unweighted directed graph of 1000000 nodes and I would like to find all simple paths of length 5. I know there will be very few simple paths of length 5 (maybe only one).

I see from http://en.wikipedia.org/wiki/Longest_path_problem that the parameterized complexity of determining if a graph has a path of length k is O(2^k n poly(n,k))) although I don't know if these methods will also solve my problem. Unfortunately all the methods I have found look very complicated and it seems unimplemented.

Can someone explain in more or less simple words a fast solution which I can then implement?

4

1 回答 1

2

我为最长路径编写了一个颜色编码方法的实现。但是，它只用大约 10000 个顶点的图进行了测试；此外，它可能无法找到所有大小为 5 的路径（它旨在找到一小组有趣的路径）。我也许可以根据您的目的对其进行调整，如果您有兴趣，请给我留言。

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

于 2013-07-12T20:56:53.057 回答