algorithm - 查找通过两个顶点之间的边的路径数

Question

我有一种算法可以确定在 DAG 中从每个顶点到特定顶点 t(出度等于 0)的路径数。现在我选择其他入度为 0 的特定顶点 s。我必须开发另一种算法来确定，对于每条边 (u, v)，从 s< 穿过 (u, v) 的路径数/strong> 到 t，时间复杂度为 O(|V|+|E|)。

我已经尝试修改 BFS(因为我认为使用 DFS 不可能达到解决方案)但是如果我有一条边有多条路径，它就不起作用。您能否建议或提示我如何集中精力获得解决方案？

顺便说一句，这个问题与拓扑排序有关。

提前致谢! :)

Answer 1

您的 previous question 已经有了答案查找从所有顶点到目标节点 t 的路径数。

所以，具体来说，使用这个算法，你有从 v 到 t 的#paths。
使用这个算法，你还可以找到从s到u的路径。

从s到t使用(u,v)的路径总数正好是#paths (s,u) * #paths(v,t)

---

解释:

从s 到u 的路径数由算法的正确性给出。您只有一个选择可以前进到 v，因此从 s 到 v 的路径数也是相同的数。现在，您可以使用每个 #paths(v,t) 从 v 继续到 t，总共有 #路径(s,u)*#paths(v,t)

复杂性:

该算法要求从节点a到节点b找到两倍数量的路径，每条路径都是O(V+E)，所以这个算法的复杂度也是O(V+ E)

---

附件:寻找从所有顶点到目标节点的#paths t的算法:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn
create new array of size t, let it be arr
init: arr[t] = 1
for i from t-1 to 1 (descending, inclusive):
    arr[i] = 0  
    for each edge (v_i,v_j) such that i < j <= t:
         arr[i] += arr[j]

原始问题中的证明和分析(链接)。