floyd.m

用 Floyd 算法求任意两点间的最短路径及最短路长. D0 是图的邻接矩阵

function [C,D]=FLOYD(D0)
% 用 Floyd 算法求任意两点间的最短路径及最短路长. D0 是图的邻接矩阵(其中主对角线为零, 两不同的点无边相连用 inf 表示), 输出路径为 cell C, 及最短路程矩阵 D 
N=length(D0); C=cell(N); 
for II=1:N for IJ=1:N C{II,IJ}=strcat(int2str(II),'-',int2str(IJ)); end; end; % 标记初始路径
for K=1:N % 叠代并标记路径
    D=min(D0,repmat(D0(:,K),1,N)+repmat(D0(K,:),N,1));%Floyd 算法: D(I,J)等于 D0(I,K)与 D0(K,J)之和与D0(I,J)两者之较小者
    [II,IJ]=find(D<D0); % 求距离改变的行,列下标
    s=length(IJ);% 改变的量的个数
    for ii=1:s   C{II(ii),IJ(ii)}=strcat(C{II(ii),K},C{K,IJ(ii)}(length(int2str(K))+1:end)); end % 连接路径 
    D0=D; % 将改变了的矩阵 D 作为初始矩阵 D0
end