5

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

请解释!

4

1 回答 1

3

我无法理解的是,用 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), 其特征值和特征向量对图的结构提供了一些见解(远远超过路径矩阵本身!)。

于 2013-07-25T14:14:34.223 回答