allspath(A)

% ALLSPATH - solve the All Pairs Shortest Path problem
% 
% Rapidly returns the shortest node-to-node distance along the edges of a
% graph, for all nodes in the graph.
% 
% USAGE: B = allspath(A)
% 
% A = input distance matrix between nodes
% B = shortest path distance matrix between all nodes
% 
% Notes: (1) For a graph with n nodes, A is an n-by-n distance matrix
%            giving the distances between adjacent nodes. Since the
%            distance from point i to point j is the same as the distance
%            from point j to point i, A must be a symmetric matrix
%        (2) The distance from a node to itself can either be entered as
%            zero or infinity. (Either will produce a correct result.) This
%            means that the diagonal elements of the matrix A must all be
%            either zero or infinity.
%        (3) The distance between nodes that are not adjacent to each
%            other must be entered as either zero or infinity. (Either will
%            produce a correct result.) This means that the (i,j) and (j,i)
%            elements of A, where i and j are non-adjacent nodes, must
%            all be either zero or infinity.
%        (4) If the input graph is not "connected," meaning that some
%            nodes cannot be reached from other nodes no matter how
%            many edges are traversed, then the distances between nodes
%            that cannot be connected will be returned as infinite.
%        (5) Distances between a node and itself are returned as zero.
%        (6) This function codifies an original algorithm created by
%            the author.
%        (7) No warranties; use at your own risk.
%        (8) Written by Michael Kleder, October 2005.
%        (9) Modified to remove "pdist" from example, May 2007.
% 
% EXAMPLE:
%
% % nodes:
% xy = [.73 .13;.41 .21;.74 .61;.27 .63;.44 .37;...
%     .93 .58;.68 .45;.21 .04;.8 .65;.5 .2];
% % adjacency matrix:
% A=[ 0 0 0 1 0 1 1 1 0 0
%     0 0 0 1 0 0 0 0 0 0
%     0 0 0 0 0 0 0 0 1 0
%     1 1 0 0 0 0 1 0 0 0
%     0 0 0 0 0 0 0 0 0 1
%     1 0 0 0 0 0 0 0 0 0
%     1 0 0 1 0 0 0 0 1 0
%     1 0 0 0 0 0 0 0 0 0
%     0 0 1 0 0 0 1 0 0 0
%     0 0 0 0 1 0 0 0 0 0];
% % distance matrix:
% [a,b]=ndgrid(1:10);
% x=xy(:,1);y=xy(:,2);A=A.*sqrt((x(a)-x(b)).^2+(y(a)-y(b)).^2);
% clc
% disp('Pairwise Distance Matrix (Nonzero for Adjacent Nodes):')
% disp(num2str(A,3))
% % plot the graph:
% figure;gplot(A,xy);hold on
% % plot node numbers:
% h=[];
% for n=1:10;h(n)=text(xy(n,1),xy(n,2),num2str(n));end
% set(h,'fontsize',16)
% % shortest path distance matrix
% disp(' ')
% disp('All Pairs Shortest Path Matrix for All Nodes:')
% disp(num2str(allspath(A),3))

function B = allspath(A)
B=full(A);
B(B==0)=Inf;
C=ones(size(B));
iter=0;
while any(C(:))
    C=B;
    B=min(B,squeeze(min(repmat(B,[1 1 length(B)])+...
        repmat(permute(B,[1 3 2]),[1 length(B) 1]),[],1)));
    C=B-C;
end
B(logical(eye(length(B))))=0;
return