如何从邻接矩阵MATLAB距离矩阵矩阵、距离、MATLAB
我有邻接矩阵让它被称为一个大小为N * N
I have adjacency matrix let it be called A size n*n
其中， A（K，J）= A（J，K）= 1 如果 K，J 是连接1跳。
Where A(k,j)=A(j,k)=1 if k,j are connected in 1 hop.
现在看起来，如果我拿
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
这是正确的呢？
Is this right at all?
我尝试着用一些简单的图表，它看起来合法的。
I tried it with some simple graphs and it looks legit
我可以利用这一点来创建距离矩阵？
Can I use this fact to create distance matrix?
其中距离矩阵将显示从第j跳的最小数目为k
Where distance matrix will show the minimum number of hops from j to k
P.S：
如果是合法的，我会很乐意了解为什么它是正确的，现在却发现在谷歌资讯
If it legit I will be happy to understand why it is right, did now find info in Google
推荐答案
是的，这是完全正确的：邻接矩阵的条目为您提供了顶点之间的连接。邻接矩阵的力量是串联散步。该 IJ 的日的的项氏/ code>的日的力量邻接矩阵告诉你的阶层数量的长度 K 从顶点我顶点Ĵ。
Yes, this is perfectly right: the entries of the adjacency matrix gives you the connections between vertices. Powers of the adjacency matrix are concatenating walks. The ijth entry of the kth power of the adjacency matrix tells you the number of walks of length k from vertex i to vertex j.
这可以很容易地通过归纳证明。
This can be quite easily proven by induction.
请注意，邻接矩阵的权力计数的数量I→Ĵ走，不是路（步行可以重复顶点，而路径不能）。所以，要创建一个距离矩阵，你需要iterativerly电源的邻接矩阵，并尽快在 IJ 的日的元素是非零你有分配在距离矩阵的距离 K 。
Be aware that the powers of the adjacency matrix count the number of i→j walks, not paths (a walk can repeat vertices, while a path cannot). So, to create a distance matrix you need to iterativerly power your adjacency matrix, and as soon as a ijth element is non-zero you have to assign the distance k in your distance matrix.
下面是一个尝试：
% 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算法。
Note that if you are searching for the shortest paths in a graph, you can also use Dijkstra's algorithm.
最后，注意，这是完全comptatible与稀疏矩阵。作为邻接矩阵是经常良好候选稀疏矩阵，它可能是在性能方面非常有益的。
Finally, note that this is completely comptatible with sparse matrices. As adjacency matrices are often good candidates for sparse matrices, it may be highly beneficial in terms of performance.
最好的，
