如何计算R中矩阵运算的最短路径？

Question

我有一个表示图形的相邻矩阵。

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会受不了迭代。所以我正在寻找在矩阵运算中执行floyd算法的方法。

附加参考

Thereotically，大家可以参考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 

Answer 1

你让我留下一个答案。虽然我不完全确定你在找什么。您应该访问allShortestPaths的帮助页面。使用函数看起来相当简单，它可以采用方形矩阵并找到最近的路径。

在包e1071为allShortestPaths的代码如下

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> 

了解更多信息，请查看帮助页面。