algorithm - 从给定顶点开始的所有长度为 k 的路径

Question

假设我有一个边成本(实数)∈(0,1)的有向图 G(V,E)。对于给定的 i，我需要找到所有顶点对 (i,j) 从i 表示“匹配”。如果存在从 i 到 j 的有向路径且长度恰好为 k(k 是给定的相对较小的数字，可以视为常数)且成本 >=C，则两个顶点 (i,j) 匹配(C 是给定的数字)。路径的成本计算为其边的乘积。例如，如果从 i 开始到 j 的长度为 2 的路径包含边 e1 和 e2，则 CostOfpath=cost(e1)*cost (e2).

这必须在 O(E+V*k) 中完成。所以我想修改 DFS 算法，更新从给定起始顶点 i 到它们达到 k 的长度的距离。如果他们不这样做，那么我们无法匹配。但是我很难找到我可以在 DFS 中修改的内容。有什么想法吗？

Answer 1

当您需要考虑其中边数固定的路径时，动态规划通常会提供帮助(而其他方法通常会失败)。

我们用 dp[v][j] 表示从顶点 i(固定)到顶点 v 的路径的最大成本恰好 j 条边。

对于起始值，您可以为 j==1 设置值:dp[v][1] 是从 i 到 v(如果不存在这样的边，则为 0)。或者，如果您考虑一下，很明显您可以为 j==0 设置值，而不是 j==1:dp[i][0 ] 为 1，而对于 v!=i，dp[v][0] 可以设置为零。

现在，如果您有一些 j 的值，则很容易计算 j+1 的值:

dp[v][j+1] = max( dp[v'][j] * cost((v', v)) )

这与 Ford-Bellman's algorithm 非常相似，只是后者不需要跟踪边数，可以使用一维数组。

这为您提供了 O((E+V)*k) 中的解决方案。不完全符合您的要求，但我怀疑 O(E+V*k) 中是否存在解决方案。

(在上面的解决方案中，我假设常数C是正的，因此零成本路径相当于路径绝对不存在。如果需要，您可以具体说明C==0 大小写。)