floyd.m

floyd算法

function Floyd
%%Floy算法用于求任两点间的最短路径
%%输入数据
n=input('请输入结点的个数n=');
m=input('请输入边的个数m=');
for k=1:n
   dian(k).name=strcat('v',num2str(k));
end
for k=1:m
   bian(k).qianqu=input('边的前驱：','s');
   bian(k).houji=input('边的后继：','s');
   bian(k).value=input('边的权值：');
end
%%初始化，制最短路径表D以及最短路径长度表P
for k1=1:n
   for k2=1:n
      if k1==k2
         D(k1,k2)=0;
      else 
         for k3=1:m
             if bian(k3).qianqu(2)==num2str(k1)&bian(k3).houji(2)==num2str(k2)
                D(k1,k2)=bian(k3).value;
                P(k1,k2)={strcat(dian(k1).name,dian(k2).name)};%%将P设置成元胞数组，利于之后的显示
             end
         end
      end
   end
end 
for k1=1:n
    for k2=1:n
        if k1~=k2&D(k1,k2)==0%%这个判断限制了这样一种情况：两地有距离但权值为0，如遇到这种情况需要改进算法
           D(k1,k2)=inf;
        end
    end
end
%%求解任两点间的最短路径
for k1=1:n
    for k2=1:n
        if k1~=k2
           for k3=1:n
               if k1~=k3
                  if (D(k2,k1)+D(k1,k3))<D(k2,k3)
                     D(k2,k3)=D(k2,k1)+D(k1,k3);
                     P(k2,k3)={strcat(P(k2,k1),P(k1,k3))};
                  end
               end
          end
       end
    end
end 
D=num2cell(D);
cellplot(D),figure;cellplot(P);