arrays - 计算 DAG 中所有长度的路径数

Question

假设您有一个未加权的 DAG 和两个顶点，start s 和 endt 。问题是计算从 s 到 t 的长度为 1, 2, 3...N-1 的路径有多少条，其中N 是 DAG 中的顶点数。

---

我的方法:

• 构建一个大小为N*N的矩阵d，其中d[u][k]是路数在 k 步内从 s 到达 u，并设置 d[s][0] = 1

• 找到DAG的拓扑排序TS

• 现在，对于 TS

  中的每个顶点 u
  • 将数组d[u]克隆为a
  • 将 a 中的每个元素右移 1(即，在左边插入 0，舍弃最右边的元素)
  • 对于 u 的每个相邻顶点 v，将数组 a 添加到数组 d[v]<

• 答案是d[t]

这似乎适用于 O(V+EV)。我想知道是否有更高效的O(V+E)方式？

Answer 1

最优算法很有可能 O(VE)。然而，使用允许多次访问顶点的 BFS 可以实现更简单的实现(在大多数实际情况下，这将使用比 O(V^2) 更少的内存。