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

Count number of Node - Disjoint Paths between any two nodes in directed graph such that there distance is <=K

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

有关节点的详细信息 - 不相交路径可以是

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

如果有人有想法用DFS解决它,请分享。

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
 }  

}