graph - 从邻接矩阵计算路径矩阵

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），其每个顶点 A[i][j] 基本上表示从 i 到 j 的路径长度为 2 的路径数。

类似地，如果我们将邻接矩阵乘以 3 次，即得到 A^3（比如 AM3），其每个顶点 A[i][j] 基本上表示从 i 到 j 的路径长度为 3 的路径数……以此类推。

现在我们定义一个矩阵 X 使得：

X=AM1+AM2+AM3...AMn（其中n是顶点数）

根据这个 X 矩阵，我们通过将所有非零顶点替换为 1 来计算路径/到达能力矩阵。

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

我知道 X[i][j] 表示路径数，路径长度为 n 或小于 n，从 i 到 j，但为什么我们只计算直到 n，而不是更多或更少？

请解释！

Answer 1

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

如果A^k为我们提供了步骤i->j之后的路径数k，非零数字意味着路径矩阵中的相应条目应该为 True，因为至少存在一条路径。现在对于k=1(loops), k=2, k=3... 一直到k=N...

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

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

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