CODEWITHSUNDEEP
algorithmmatlabnetwork-programmingmatrixlogic
JohnnyF
JohnnyF

Reputation: 1101

How to get distance matrix from Adjacency matrix matlab

I have adjacency matrix let it be called A size n*n

Where A(k,j)=A(j,k)=1 if k,j are connected in 1 hop.

Now it look that if I take

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?

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

Upvotes: 5

Views: 5651

Answers (1)

LowPolyCorgi
LowPolyCorgi

Reputation: 5188

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.

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.

Here is a try:

% 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

Note that if you are searching for the shortest paths in a graph, you can also use Dijkstra's algorithm.

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.

Best,

Upvotes: 7

Related Questions