algorithm - 稀疏循环图中的最长简单路径

Question

给定：一个未加权的有向图 (G=(E,V))，它可以包含任意数量的循环。

目标：对于所有顶点，我想要到 V 中某个目标顶点 X 的最长简单路径

算法思路：

For each v in V
  v.distanceToTarget = DepthFirstSearch(v)
Next

DepthFirstSearch(v as Vertex)
  if v = target then
    'Distance towards target is 0 for target itself
    return 0
  elseif v.isVisitedInCurrentDFSPath then
    'Cycle found -> I wont find the target when I go around in cycles -> abort
    return -infinity
  else
    'Return the maximum Distance of all Successors + 1
    return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v) )) + 1
  end if

这对所有情况都正确吗？（假设可以从每个顶点到达目标）

我的图中的边数非常少。假设 |E| <= 3*|V| 持有。我将如何计算平均时间复杂度？

谢谢！

Answer 1

时间复杂度是关于哪些值对您的运行时间影响最大​​。在您的情况下，您评估 v 和目标之间的所有可能路径。这基本上是 O（路线数）。现在你需要弄清楚如何用 E 和 V 来表示所有可能路线的数量。

最有可能的结果是 O(exp(E)) 或 O(exp(V))，因为当您添加新的可能路由时，通过每个节点/顶点的路由数量呈指数增长。

编辑：我错过了一个细节，你要求平均时间复杂度，这意味着摊销复杂度。但是由于您的算法总是评估所有可能的路线，因此最坏情况的复杂性与平均复杂性相同。