dist(g,v,w) and dist(g,v) --- find distance(s) between vertices The form dist(g,v,w) finds the distance between vertices v and w. The form dist(g,v) returns a vector distance from v to all other vertices in the graph. The form dist(g) returns an n-by-n matrix whose ij entry is the distance between vertices i and j. The code for all pairs shortest distance was written by Michael Kleder and found on the Mathwork's MATLAB Central file exchange.
0001 function d = dist(g,v,w) 0002 % dist(g,v,w) and dist(g,v) --- find distance(s) between vertices 0003 % The form dist(g,v,w) finds the distance between vertices v and w. 0004 % The form dist(g,v) returns a vector distance from v to all other vertices 0005 % in the graph. 0006 % The form dist(g) returns an n-by-n matrix whose ij entry is the distance 0007 % between vertices i and j. 0008 % 0009 % The code for all pairs shortest distance was written by Michael Kleder 0010 % and found on the Mathwork's MATLAB Central file exchange. 0011 0012 0013 if nargin == 3 0014 dd = dist(g,v); 0015 d = dd(w); 0016 return 0017 end 0018 0019 n = nv(g); 0020 0021 0022 if nargin==1 0023 d = alltoall(g); 0024 return 0025 end 0026 0027 d = onetoall(g,v); 0028 0029 0030 % this subroutine was written by Michael Kleder and was found on The 0031 % Mathwork's MATLAB Central file exchange. I think my new alltoall is 0032 % faster, though. 0033 % 0034 % function B = allspath(A) 0035 % B=full(double(A)); 0036 % B(B==0)=Inf; 0037 % C=ones(size(B)); 0038 % iter=0; 0039 % while any(C(:)) 0040 % C=B; 0041 % B=min(B,squeeze(min(repmat(B,[1 1 length(B)])+... 0042 % repmat(permute(B,[1 3 2]),[1 length(B) 1]),[],1))); 0043 % C=B-C; 0044 % end 0045 % B(logical(eye(length(B))))=0; 0046 % return 0047 0048 0049 % This is my replacement for allspath; I think this is faster for large 0050 % sparse graphs. 0051 function d = alltoall(g) 0052 n = nv(g); 0053 d = zeros(n,n); 0054 for v=1:n 0055 d(:,v) = dist(g,v); 0056 end 0057 return 0058 0059 0060 % This is a function that finds the shortest distance from v to all other 0061 % vertices in a graph 0062 function d = onetoall(g,v) 0063 A = double(matrix(g)); 0064 n = nv(g); 0065 vec = zeros(n,1); 0066 vec(v) = 1; 0067 d = inf*ones(1,n); 0068 d(v) = 0; 0069 0070 count = 0; 0071 while true 0072 count = count + 1; 0073 newv = (A*vec + vec)>0; 0074 morev = newv - vec; 0075 if (nnz(morev)==0) 0076 break 0077 end 0078 d(find(morev))=count; 0079 vec = newv; 0080 end 0081 return