floyd.m

求最短路径的最短距离！功能强大···不容置疑

function [d,path]=floyd(a,sp,ep)
% floyd   - 最短路问题 
% 
% Syntax: [d,path]=floyd(a,sp,ep) 
% 
% Inputs: 
%    a    - 距离矩阵是指i到j之间的距离，可以是有向的 
%    sp   - 起点的标号 
%    ep   - 终点的标号 
% 
% Outputs: 
%    d    - 最短路的距离 
%    path - 最短路的路径 
% 
% Example: 
%     a =[
%         0   50 Inf 40 25 10 ;
%         50 0   15 20 Inf 25 ;
%         Inf 15 0   10 20 Inf ;
%         40 20 10 0 10 25 ;
%         25 Inf 20 10 0   55 ;
%         10 25 Inf 25 55 0 ];
%      [d,path]=floyd(a,2,5)
% 
% 
% Other m-files required: none 
% Subfunctions: none 
% MAT-files required: none 
% 
% See also: OTHER_FUNCTION_NAME1, OTHER_FUNCTION_NAME2

% Author: Xiaoyong Ren
%Packaging Engineering, Xi'an University of Technology . 
% email :[e-mail] 
% QQ: 170071606 
% Website: http://bokoo.blogbus.com 
% December 2004; Last revision: 24-May-2005

%------------- BEGIN CODE -------------- 
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
   for j=1:n
       if D(i,j)~=inf
           path(i,j)=j; %j是i的后续点
       end
   end
end

for k=1:n
   for i=1:n
      for j=1:n
         if D(i,j)>D(i,k)+D(k,j)
            D(i,j)=D(i,k)+D(k,j);
            path(i,j)=path(i,k);
         end
      end
   end
end

p=[sp];
mp=sp;
for k=1:n
    if mp~=ep
        d=path(mp,ep);
        p=[p,d];
        mp=d;
    end
end
d=D(sp,ep);
path=p;