function D1 = floyd(D, verbose)

% floyd - compute shortest distances on a 
%   graph using Floyd algorithm.
%
%   D1 = floyd(D, verbose);
%
%   The matrix A is the weighted adjacency matrix
%
%   Copyright (c) 2004 Gabriel Peyré

if nargin==1
    verbose = 1;
end

N = length(D);

if verbose
    %h = waitbar(0,'Computing shortest distances');
end
for i=1:N
    for j=1:N
        D1(i,j)=D(i,j);
    end
end
for i=1:N
    D1(i,i)=0;
end
for k=1:N
    for i=1:N
        for j=1:N
            if D1(i,k)+D1(k,j)<D1(i,j)
                D1(i,j)=D1(i,k)+D1(k,j);
            end
        end
    end
     %D = min(D,repmat(D(:,k),[1 N])+repmat(D(k,:),[N 1])); 
     
     %if verbose
     %    waitbar(k/N)
     %end
 end
if verbose
    %close(h);
end

D1 = D;