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

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个邻接矩阵，称为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中找到了信息

回答：

是的，这是完全正确的：邻接矩阵的条目为您提供了顶点之间的连接。邻接矩阵的幂是级联的游程。本ij次 的进入k次 邻接矩阵的力量告诉你

散步的数量 长度k从顶点i到顶点j。

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

请注意，邻接矩阵的幂计算i→j步行次数，而不是路径（步行可以重复顶点，而路径不能重复）。因此，要创建一个距离矩阵，您需要迭代地对邻接矩阵进行加电，并且一旦ij

th 元素不为零，就必须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的算法。

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

最好，

以上是 如何从邻接矩阵Matlab获取距离矩阵 的全部内容， 来源链接： utcz.com/qa/425577.html

回到顶部