如何計算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> 

瞭解更多信息，請查看幫助頁面。