Как получить матрицу расстояний от матрицы смежности MATLAB

Question

У меня есть матрица смежности пусть это будет называется Размер п * п

Где 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 до к

PS:

Если законно я буду счастлив, чтобы понять, почему это правильно, так и в настоящее время найти информацию в Google

Answer 1

Да, это совершенно правильно: записи матрицы смежности дают вам соединения между вершинами. Полномочия матрицы смежности - конкатенирование прогулок. ijй вхождение kго власти матрицы смежности говорит вам количества прогулок длина k от вершины к вершине ij.

Это может быть довольно легко доказано индукцией.

Помните, что полномочия матрицы смежности подсчитывают количество проходов i→j, а не дорожек (прогулка может повторять вершины, а путь не может). Таким образом, чтобы создать матрицу расстояний, вам нужно итераторно управлять своей матрицей смежности, и как только элемент ijth не равен нулю, вы должны назначить расстояние 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. Поскольку матрицы смежности часто являются хорошими кандидатами для разреженных матриц, это может быть очень полезно с точки зрения производительности.

Бест,