How to calculate shortest path with matrix operation in R?

Question

I've an adjacent matrix representing a graph.

M

   1  2  3  4...

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

I want to perform Floyd's algorithm to calculate the shortest path between each pair of vertices.

And I can definitely iterate over them in a O(N3) complexity.

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

However when n = 10^3, R will not stand the iteration. So I'm looking for ways to perform floyd algorithm in matrix operations.

Additional Reference

Thereotically, we can refer to MIT Isomap mat file.

But I'm still confused at how to perform "repmat" in R, which replicate the mat several times.

%%%%% 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

Answer 1

You asked me to leave an answer. I'm not entirely sure what you're looking for, though. You should visit the help page for allShortestPaths. It looks pretty straightforward to use the function, which can take in a square matrix and find the shorest paths.

the code for allShortestPaths in the package e1071 is as follows

function (x) 
{
x <- as.matrix(x)
x[is.na(x)] <- .Machine$double.xmax
x[is.infinite(x) & x > 0] <- .Machine$double.xmax
if (ncol(x) != nrow(x)) 
    stop("x is not a square matrix")
n <- ncol(x)
z <- .C("e1071_floyd", as.integer(n), double(n^2), as.double(x), 
    integer(n^2), PACKAGE = "e1071")
z <- list(length = matrix(z[[2]], n), middlePoints = matrix(z[[4]] + 
    1, n))
z$length[z$length == .Machine$double.xmax] <- NA
z
}
<environment: namespace:e1071>

for more information, check out the help page.