从邻接矩阵计算路径矩阵

Question

我正在学习从邻接矩阵（如AM1）计算路径矩阵的方式。

图G的与n个顶点的路径矩阵是一个布尔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 [i] [j]基本上代表从i到j的路径长度3的路径数的A^3（也就是AM3）。等等。

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

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

从这个X矩阵我们通过将所有非零顶点替换为1来计算路径/伸展能力矩阵。

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

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

请解释一下！

Answer 1

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

如果A^k给我们的从i->j路径后k步骤的数量，一个非零数意味着，在路径矩阵中的对应条目应该是真实的，因为至少存在一个路径。现在，这必须k=1（环路），是真实的k=2，k=3 ...一路k=N ...

但是为什么我们只计算到N，没有多还是少？

如果有来自i->j与只具有N个顶点的曲线的路径，最坏的情况是，存在着需要每个中间顶点，即，N-1的步骤，因此需要的A^N的计算的路径。

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