计算有向图中任意两个节点之间的节点数 - 不相交路径，使得距离为 <=K

Question

我们如何计算任意两个节点之间的节点 - 不相交路径的数量，以使两个节点之间的距离最大为 K？

有关节点 - 不相交路径的详细信息可以在这里找到。

我们得到一个有向图，其中我们必须计算节点的数量 - 从顶点u到v的不相交路径，使得它们之间的最大节点数为 K - 2(u 和 v 从 K 递减，因此 K - 2(。图中的顶点数最多可以大于 10^5，边可以是 6 * 10^5。我想到为每个节点实现 BFS，直到与源节点的最大距离小于 K。但我没有得到实施的想法。有人请帮我吗？

如果有人有使用DFS解决它的想法，请分享。

Answer 1

DFS是解决此类问题的关键。我们可以使用 DFS 轻松枚举 2 个顶点之间的所有可能路径，但我们必须注意距离约束。

我的算法将遍历的边数视为约束。您可以轻松地将其转换为遍历的节点数。把它当作一种练习。

我们跟踪可变e遍历的边数。如果e大于 K - 2，我们终止递归DFS调用。

为了保持已访问顶点，我们保留了一个boolean数组visited。但是，如果递归调用在没有找到成功路径的情况下终止，我们将丢弃对数组visited所做的任何更改。

只有当递归DFS调用成功找到路径时，我们才会为程序的其余部分保留visited数组。

因此，该算法的伪代码将是：

main function()
{
 visited[source] = 1     
 e = 0//edges traversed so far.
 sum = 0// the answer
 found = false// found a path.
 dfs(source,e)
 print sum
 .
 .
 .
}
dfs(source,e)
{
 if(e > max_distance)
 {      
  return
 }
 if(e <= max_distance and v == destination)
 {
  found = true
  sum++      
  return
 }
 for all unvisited neighbouring vertices X of v
 {
  if(found and v != source)
   return;
  if(found and v == source)
  {
   found = false
   visited[destination] = 0
  }
  visited[X] = 1
  dfs(X , e + 1)
  if(!found)
   visited[X] = 1
 }  
}