1

グラフを表す隣接行列があります。

M

   1  2  3  4...

   1  -  1  3  2
   2  1  -  3  1
   3  4  2  -  3
   .
   .

フロイドのアルゴリズムを実行して、頂点の各ペア間の最短経路を計算したいと考えています。

そして、O(N3) の複雑さでそれらを確実に繰り返すことができます。

for ( i in 1 : n )
  for ( j in 1 : n )
    for ( k in 1 : n )
      Floyd...

ただし、n = 10^3 の場合、R は反復に耐えられません。そこで、行列演算でフロイド アルゴリズムを実行する方法を探しています。

追加の参照

理論的には、 MIT Isomap mat fileを参照できます。

しかし、マットを数回複製するR で「repmat」を実行する方法については、まだ混乱しています。

%%%%% Step 2: Compute shortest paths %%%%%
disp('Computing shortest paths...'); 

% We use Floyd's algorithm, which produces the best performance in Matlab. 
% Dijkstra's algorithm is significantly more efficient for sparse graphs, 
% but requires for-loops that are very slow to run in Matlab.  A significantly 
% faster implementation of Isomap that calls a MEX file for Dijkstra's 
% algorithm can be found in isomap2.m (and the accompanying files
% dijkstra.c and dijkstra.dll). 

tic; 
for k=1:N
     D = min(D,repmat(D(:,k),[1 N])+repmat(D(k,:),[N 1])); 
     if ((verbose == 1) & (rem(k,20) == 0)) 
          disp([' Iteration: ', num2str(k), '     Estimated time to completion: ', num2str((N-k)*toc/k/60), ' minutes']); 
     end
end
4

1 に答える 1