如何从邻接矩阵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 的最小跳数

P.S:

如果它是合法的，我会很乐意理解为什么它是正确的，现在在 Google

中找到了信息

Answer 1

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

的长度 k 的行走

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

请注意，邻接矩阵的幂计算的是 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

请注意，如果您要搜索图中的最短路径，也可以使用 Dijkstra's algorithm。

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

最佳，

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

How to get distance matrix from Adjacency matrix matlab

algorithm

networking

matlab

logic

matrix