Matlab 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Matlab
标  题: floyd算法 zz
发信站: 哈工大紫丁香 (Sun Dec 14 09:02:22 2003), 站内信件

发信站: 饮水思源

【转】
 floyd算法
最近两天做了一个图论的题目，其中有一个求最短路的，我用的是floyd算法，现贴出来

，供大家参考。
-------------------------------------------------------------------
function [ler,r]=floyd(w)
%[ler,r]=floyd(w)
%w;邻接矩阵
%ler:为所得的最短路矩阵
%参考文献：谢政，李建平：网络算法与复杂性理论.国防科技出版社.1995,第一版。
n=size(w,1);
u.m_1=w;
r.m_1=ones(n,1)*[1:n];

m=1;
while m~=n+1
   for i=1:n
      for j=1:n
           if u.m_1(i,j)<=u.m_1(i,m)+u.m_1(m,j)
               r.m(i,j)=r.m_1(i,j);
           else
               r.m(i,j)=r.m_1(i,m);
           end
           u.m(i,j)=min(u.m_1(i,j),u.m_1(i,m)+u.m_1(m,j));
      end
   end
    u.m_1=u.m;
    r.m_1=r.m;
    m=m+1;
end

ler=u.m;
--------------------------------------------------------------------------
最短轨：
function [road]=findroad(var1,var2,r)
%road=cell(size(r.m));
rola=0;
road=var1;
while rola~=var2
    rola=r.m(var1,var2);
    road=[road rola];
end



--
╔═══════════════════╗
║★★★★★友谊第一  比赛第二★★★★★║
╚═══════════════════╝

※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 202.118.229.162]