如何从邻接矩阵matlab得到距离矩阵

我有一个邻接矩阵，将其称为 A 大小 n*n

Where A(k,j)=A(j,k)=1 if k,j在 1 跳中连接。

现在看来，如果我采取

Dist=double(A)*double(A)>0 %getting all two hops connectivity
Dist=double(Dist)*double(A)>0 %getting all three hops connectivity 
Dist=double(Dist)*double(A)>0 %getting all four hops connectivity

这是正确的吗？

我尝试了一些简单的图表，它看起来合法

我可以使用这个事实来创建距离矩阵吗？

其中距离矩阵将显示从 j 到 k 的最小跳数

P.S:

如果它合法，我会很高兴理解为什么它是正确的，现在在谷歌中找到了信息

是的，这是完全正确的：邻接矩阵的条目为您提供了顶点之间的连接。邻接矩阵的幂是串联游走。这ijth的条目kth邻接矩阵的幂告诉你步行次数长度k从顶点i到顶点j.

这可以通过归纳法很容易地证明。

请注意，邻接矩阵的幂计算了i→j步行，而不是路径（步行可以重复顶点，而路径则不能）。因此，要创建距离矩阵，您需要迭代地增强邻接矩阵，并且一旦ijth元素非零，您必须指定距离k在你的距离矩阵中。

这是一个尝试：

% Adjacency matrix
A = rand(5)>0.5

D = NaN(A);
B = A;
k = 1;
while any(isnan(D(:)))

    % Check for new walks, and assign distance
    D(B>0 & isnan(D)) = k;

    % Iteration
    k = k+1;
    B = B*A;
end

% Now D contains the distance matrix

请注意，如果您要搜索图中的最短路径，您还可以使用迪杰斯特拉算法.

最后，请注意，这完全兼容稀疏矩阵。由于邻接矩阵通常是稀疏矩阵的良好候选者，因此它在性能方面可能非常有益。

Best,