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

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

是的，这是完全正确的：邻接矩阵的条目为您提供了顶点之间的连接。邻接矩阵的幂是级联的游程。本

ij

次 的进入

k

次 邻接矩阵的力量告诉你
散步的数量 长度

k

从顶点

i

到顶点

j

。

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

请注意，邻接矩阵的幂计算

i→j

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

ij

th 元素不为零，就必须

k

在距离矩阵中分配距离。

尝试一下：

% Adjacency matrixA = rand(5)>0.5D = 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的算法。

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

最好，