floyd1.m

matlab中最短路问题的算法

function [D,path]=floyd1(a)
  %a是带权邻接矩阵，当i与j不相同时,若i与j相连就取其权，否则，当i与j相同时，元素取0
n=size(a,1);%设置D和path的初值
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,k)+D(k,j)<D(i,j)
             D(i,j)=D(i,k)+D(k,j);
             path(i,j)=path(i,k); 
         end
      end
    end
end