如何從鄰接矩陣MATLAB

Question

獲得距離矩陣我有鄰接矩陣讓它被稱爲尺寸爲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：

如果合法的，我會很樂意瞭解爲什麼它是正確的，沒有現在發現的信息在谷歌

Answer 1

是的，這是完全正確的：鄰接矩陣的條目爲您提供頂點之間的連接。鄰接矩陣的權力連接步行。在k次功率鄰接矩陣的ij個條目告訴你數量從頂點i走長度k的到頂點j。

這可以通過歸納很容易證明。

請注意，鄰接矩陣的冪數計算i→j散步的數量，而不是路徑（散步可以重複頂點，而路徑不能）。因此，要創建距離矩陣，您需要迭代地爲鄰接矩陣供電，並且一旦元素非零，您必須在距離矩陣中指定距離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完全兼容。由於鄰接矩陣通常是稀疏矩陣的良好候選者，因此在性能方面可能非常有益。

最佳，