floyd算法的matlab实现

floyd算法

2018.8.29
经过计算后得到的可行的算法，可以算出任意两点间的最短路程

function [dist,path]=myfloyd(a)
%寻找i,j两点最短路径
% 输入：a—邻接矩阵，元素(aij)是顶点i到j之间的直达距离，可以是有向的
% sb—起点的标号；db—终点的标号
% 输出：dist—最短路的距离；% path—最短路的路径
n=size(a,1);
m=a;
for i=1:n   %path矩阵的初始化
    for j=1:n
        path(i,j)=j;
    end
end
   
for k=1:n
    for i=1:n
        for j=1:n
            if a(i,j)>a(i,k)+a(k,j)
                a(i,j)=a(i,k)+a(k,j);
                path(i,j)=k;
            end
        end
    end
end
for sb=1:n
   for db=1:n
      t=path(sb,db);
      dist(sb,db)=m(sb,t);
       while t~=db
         p=path(t,db);        
         dist(sb,db)=dist(sb,db)+m(t,db);
         t=p;
       end
    end
end