%8.6 shortestpathcode.m function [M] = all_pairs(A) % function [M] = all_pairs(A) % % A should be the adjacency matrix of a graph, possibly weighted. % D is the induced distance between all pairs of nodes. % If there is no path from node i to j, then D(i,j) will be inf. % % A is assumed to be a directed adjacency matrix, so if you desire % the result for an undirected graph, be sure that A is symmetric. % we now need to put infs on the non-edges. % the following two lines would work if only inf*0 = 0. % % M0 = ((A+eye(length(A))) == 0); % M = A + inf*M0 % % instead, we use the following, which would be faster if A was % in sparse form--i.e. an edge list: M = inf*ones(length(A)); for i = 1:length(A), for j = 1:length(A) if (i == j | A(i,j) ~= 0) M(i,j) = A(i,j); end end end for i = 1:ceil(log2(length(A))), M = ms_mult(M,M); end ----- function [M] = ms_mult(A,B) % function [M] = ms_mult(A,B) % % Min-Sum multiplication. % % This performs a matrix multiplication on A and B, % but with product replaced by sum and sum replaced by min. % % The routine assumes that A and B have the same size, and are square. % % ms_mult is designed to work for directed graphs--to adjust it % for symmetric graphs run j = (i+1):length(M) M = zeros(size(A)); for i = 1:length(M), for j = 1:length(M), M(i,j) = min(A(i,:) + B(:,j)'); end end