f_cycle.m

清华大学运筹学课件

%negative cycle
function y=cycle(n,U); %U(i,i)=0 and U(i,j)=inf

S=zeros(n);
   for i=1:n
      for j=1:n   S(i,j)=j;   end
   end   
x=0;
for m=1:n
   for i=1:n
      for j=1:n
         if U(i,j)>U(i,m)+U(m,j)  U(i,j)=U(i,m)+U(m,j); S(i,j)=S(i,m);  end  
      end
   end
   for k=1:n
      if U(k,k)<0    x=1; 
         break
      end
   end
   if x==1
      break
   end
end 
 C=zeros(1,n+1); 
if x==1
   a=S(k,k);  C(1)=k;  j=1;
   while a~=k    j=j+1; C(j)=a;  a=S(a,k);    end
end
C(j+1)=C(1);

y=C;