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 文件。

但是我仍然对如何在 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

2

你让我留下一个答案。不过，我不完全确定您在寻找什么。您应该访问 的帮助页面allShortestPaths。使用该函数看起来非常简单，它可以接收方阵并找到最靠近海岸的路径。

allShortestPaths包中的代码e1071如下

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>

有关更多信息，请查看帮助页面。

于 2013-08-07T07:39:47.877 回答