algorithm - 从一个起始顶点开始的所有 k 个长度的路径

Question

给定一个有向图 G(V,E)，我需要找到从 i 开始到具有恰好 k 长度的任何其他顶点的所有不同路径。

我知道可以使用 O(K V^3) 中的 3D 表在 2 个顶点之间找到长度恰好为 k 的所有可能路径，因此我们可以执行此 V 次以找到所有想要的路径。但是我想知道这是否可以比 O(K V^4) 做得更好。

标签： algorithm

Answer 1

考虑使用从节点开始的有限深度优先搜索，并将搜索深度限制为k.