2

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

我试图修改 BFS（因为我认为使用 DFS 是不可能达到解决方案的）但是如果我有多个路径的优势，它就不起作用。您能否建议我或给我一个提示，告诉我如何将工作重点放在获得解决方案上？

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

提前非常感谢！:)

4

1 回答 1

1

您已经从上一个问题中得到答案，以查找从所有顶点到目标节点的路径数t。

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

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

解释：

s从到的路径数由u算法的正确性给出。您只有一个选择可以前进，因此从tov的路径数也是相同的数字。现在，您可以继续使用其中的每一个，总共为您提供svvt#paths(v,t)#paths(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]

原始问题中的证明和分析（链接）。

于 2013-08-08T12:50:37.283 回答