ford.m

10组图论编程

function y=ford(D,start,term)
%逐步逼近算法可求带有负权边的网络任2点的最短路。
%0代表重合点，inf代表无连接。
a(1,:)=[0,50,inf,40,25,10]; 
a(2,:)=[zeros(1,2),15,20,inf,25]; 
a(3,:)=[zeros(1,3),10,20,inf]; 
a(4,:)=[zeros(1,4),10,25]; 
a(5,:)=[zeros(1,5),55]; 
a(6,:)=zeros(1,6); 
a=a+a'; 
if nargin==0
   start=1;
   term=4;
   D=a;
end;
N=length(D);
[i,j]=find((D~=0)&(D~=inf));
d=D(find((D~=0)&(D~=inf)));
data=[i';j'];
u=zeros(1,N); 
u(1,:)=inf;
u(start)=0;
%u是距离标号。
%u(j)中储存从start点到j点的最短距离。
pred(start)=0;
list=[start];
while ~isempty(list)
    x=list(1);
    list(1)=[];
    [i,j]=find(data(1,:)==x);
    for e=1:length(i)
         temp=data(2,j(e));
%temp是与i相邻的且未标号的点。
         if u(temp)>(u(x)+D(x,temp))
             u(temp)=(u(x)+D(x,temp));
            list=[list,temp];
             pred(temp)=x;
         end
     end
 end
 reslut=[term];
temp1=pred(term);
while temp1~=start
   reslut=[reslut,temp1];
   temp1=pred(temp1);
end
reslut=[reslut,temp1];
y=reslut;
end