title: How to calculate shortest path with matrix operation in R?
body: <p>I've an adjacent matrix representing a graph.</p>
  
  <pre><code>M
  
     1  2  3  4...
  
     1  -  1  3  2
     2  1  -  3  1
     3  4  2  -  3
     .
     .
  </code></pre>
  
  <p>I want to perform Floyd's algorithm to calculate the shortest path between each pair of vertices.</p>
  
  <p>And I can definitely iterate over them in a O(N3) complexity.</p>
  
  <pre><code>for ( i in 1 : n )
    for ( j in 1 : n )
      for ( k in 1 : n )
        Floyd...
  </code></pre>
  
  <p>However when n = 10^3, R will not stand the iteration. So I'm looking for ways to perform floyd algorithm in matrix operations.</p>
  
  <h1>Additional Reference</h1>
  
  <p>Thereotically, we can refer to <a href="http://web.mit.edu/cocosci/isomap/code/Isomap.m" rel="nofollow">MIT Isomap mat file</a>.</p>
  
  <p>But I'm still confused at <strong>how to perform "repmat" in R</strong>, which replicate the mat several times.</p>
  
  <pre><code>%%%%% 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) &amp; (rem(k,20) == 0)) 
            disp([' Iteration: ', num2str(k), '     Estimated time to completion: ', num2str((N-k)*toc/k/60), ' minutes']); 
       end
  end
  </code></pre>