function [D] = Floyd_Warshall(D)
% Floyd-Warshall algorithm for calculating shortest paths in a graph.
% Input: 
%   weight matrix (edge weights)
% Output:
%   shortest path distances
%
% (c) 1998-2000 Josh Tenenbaum 

fprintf('--> Calculating shortest paths...\n');

N = size(D,1);
tic; 
for k=1:N
     D = min(D, repmat(D(:,k),[1 N]) + repmat(D(k,:),[N 1]));
     if (rem(k, 20) == 0)
        disp(['  Iteration: ' num2str(k) ' Estimated time to completion: ' num2str((N-k)*toc/k/60) ' minutes']); 
     end;
end;

fprintf(' done.\n');
