图中的路径数

Question

如何计算有向图中的路径数？有没有为此目的的算法？

最好的祝愿

编辑:图表不是树.

Answer 1

让A成为图的邻接矩阵G。然后A^n（即与自身A相乘n）具有以下有趣的性质：

位置(i,j)处的条目A^n等于n从顶点i到顶点的不同长度路径的数量j。

因此：

• 将图表示为邻接矩阵 A
• A反复乘以它自己直到你感到无聊
• 在每一步中：计算所有矩阵元素的总和并将其添加到结果中，从 0 开始

首先检查 G 是否包含循环可能是明智的，因为在这种情况下它包含无限多条路径。为了检测循环，将所有边缘权重设置为 -1 并使用 Bellman-Ford。

Answer 2

我不相信有什么比从根开始遍历图表更快的了。

在伪代码中 -

visit(node) {
  node.visited = true;
  for(int i = 0; i < node.paths.length; ++i) {
    ++pathCount;
    if (!node.paths[i].visited)
      visit(node.paths[i]);
  }

}