lujin.m

最短路径问题（包括Floyd算法和避圈法）的matlab程序

distance_1=[?
    ?
    ?
    ];
            
%原始数据 ：前两列为顶点编号，第3列为距离
N=???????;%总的顶点数
inf_num=10000;%代表正的无穷大
distance=inf_num*ones(N);
for k=1:length(distance_1)
    distance(distance_1(k,1),distance_1(k,2))=distance_1(k,3);
    distance(distance_1(k,2),distance_1(k,1))=distance_1(k,3);
end
complete_graph=zeros(N);
path=cell(N);
M=N+1;
for v1=1:N
    W=distance;
    temp=W(v1,:);
    W(v1,:)=W(1,:);
    W(1,:)=temp;
    temp=W(:,v1);
    W(:,v1)=W(:,1);
    W(:,1)=temp;
    S=[1];
    P=[0];
    Lamda=[0,M*ones(1,N-1)];
    T=inf_num*ones(1,N);
 while 1
     if length(S)==N
         break
     end
     R=[1:N];
     R(S)=[];
     for j=R
         if W(S(end),j)<inf_num
             if T(j)>P(end)+W(S(end),j)
                 T(j)=P(end)+W(S(end),j);
                 Lamda(j)=S(end);
             end
         end
     end
     [Y,index]=min(T(R));
     if Y<inf_num
         P=[P,Y];
         S=[S,R(index)];
     else
         break
     end
 end
 for k=2:N
     road=[k];
     while 1
         if road(end)==1
             break
         else
             road=[road,Lamda(road(end))];
         end
     end
     road=fliplr(road);
     index=find(road==v1);
     if ~isempty(index)
         road(index)=1;
     end
     road(1)=v1;
     path{v1,road(end)}=road;
 end
     [Y,index]=sort(S);
     P=P(index);
     P(1)=P(v1);
     P(v1)=0;
     complete_graph(v1,:)=P;
 end
 save complete_graph complete_graph 
 save path path