我正在学习从邻接矩阵(比如 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,而不是更多或更少?
请解释!