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 :horlab@sohu.com
% 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;
%------------- END OF CODE --------------