グラフを表す隣接行列があります。
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