从邻接矩阵计算路径矩阵

Question

我正在学习从邻接矩阵(如AM1)中计算路径矩阵的方法。

具有n个顶点的图G的路径矩阵是布尔n*n矩阵，其元素可定义为：

  p[i][j]=1(if there is a path from i to j)
  p[i][j]=0(otherwise)

我学到的步骤如下：

如果我们自己乘一个邻接矩阵A，则得到A^2(例如AM2)，它的每个顶点Ai基本上表示从i到j的路径长度2的路径数。

同样地，如果我们将一个邻接矩阵乘以3次，即得到A^3(例如AM3)，它的每个顶点Ai基本上表示从i到j的路径长度3的路径数。诸若此类。

现在我们定义一个矩阵X，这样：

X=AM1+AM2+AM3...AMn (其中n是顶点数)

从这个X矩阵中，我们用1代替所有非零顶点来计算路径/到达能力矩阵。

我无法理解的是，用1替换所有非零顶点是如何给出路径矩阵的？以及为什么我们计算或将所有矩阵加到AMn中。

我知道Xi代表从i到j的路径长度n或小于n的路径数，但为什么我们只计算到n，而不是多或少？

请解释一下！

Answer 1

我无法理解的是，用1替换所有非零顶点是如何给出路径矩阵的？

如果A^k给出了i->j在k步骤之后的路径数，一个非零的数字意味着路径矩阵中相应的条目应该是真，因为至少有一条路径存在。对于k=1 (循环)，k=2，k=3.一直到k=N..。

但为什么我们只计算到n，而不是更多或更少？

如果在只有N个顶点的图上有一条来自i->j的路径，最坏的情况是有一条路径占用每个中间顶点，即N-1步，因此需要计算A^N。

请注意，还有其他更便宜的方法来计算所谓的路径矩阵.本质上(对于无向图)，您正在寻找图的连通元件，这可以通过深度优先搜索在线性时间内完成。要计算所有的A^k，每个乘法将需要大约O(N^3)时间，N时间的总和约为O(N^4)。这可以通过矩阵O(N^3)的对角化来避免，它的特征值和特征向量给出了图的结构(远大于路径矩阵本身！)。