如何从邻接矩阵matlab获取距离矩阵

Question

我有邻接矩阵让它被称为 A 大小 n*n

其中A(k,j)=A(j,k)=1如果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 的最小跳数

PS：

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

Answer 1

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

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

请注意，邻接矩阵的幂计算的是i?j步行次数，而不是路径（步行可以重复顶点，而路径不能）。因此，要创建距离矩阵，您需要迭代地为邻接矩阵供电，并且只要ij第一个元素不为零，您就必须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

请注意，如果您要在图中搜索最短路径，您还可以使用Dijkstra 算法。

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

最好的事物，