最短路.txt

各类人工智能算法源代码哦

1。最小费用最大流
function [Max_flow,F]=min_cost(tk,n)
% 最小费用最大流[Max_flow,F]=min_cost(tk,n)
% 例1:
% n=5;
% tk=[0 0 10 4 8 1 0 inf 0 inf 
% 0 inf 0 0 0 inf 2 6 7 1 
% 0 inf 5 2 0 0 10 3 0 inf 
% 0 inf 0 inf 0 inf 0 0 4 2 
% 0 inf 0 inf 0 inf 0 inf 0 0 ];
% [Max_flow,F]=min_cost(tk,n)
% 例2:
% n=6; 
% tk=[0 0 4 1 5 3 0 inf 0 inf 0 inf
% 0 inf 0 0 1 1 3 3 0 inf 0 inf
% 0 inf 0 inf 0 0 0 inf 2 4 0 inf
% 0 inf 0 inf 0 inf 0 0 0 inf 5 2
% 0 inf 0 inf 0 inf 1 1 0 0 2 4
% 0 inf 0 inf 0 inf 0 inf 0 inf 0 0];
% [Max_flow,F]=min_cost(tk,n)
% 例3:
% n=6; 
% tk=[0 0 3 2 4 1 0 inf 0 inf 0 inf
% 0 inf 0 0 0 inf 6 5 4 3 0 inf
% 0 inf 0 inf 0 0 5 4 3 3 0 inf
% 0 inf 0 inf 0 inf 0 0 0 inf 7 0
% 0 inf 0 inf 0 inf 0 inf 0 0 3 0
% 0 inf 0 inf 0 inf 0 inf 0 inf 0 0];
% [Max_flow,F]=min_cost(tk,n)

%===========子函数1==============
function [C,B]=CB(n,tk)
   for i=1:n
      for j=1:n
          C(i,j)=tk(i,2*j-1);
          B(i,j)=tk(i,2*j);
      end
   end
end
%===========子函数2==============
function[pa,flag]=short(B,s,v)   
%求最短路
n=size(B,1);
D=B;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
%做n迭代,每次迭代均更新D(i,j)和path(i,j)
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
i=1;
pa(i)=s;
i=i+1;
flag=1;
while s~=v
    if path(s,v)==0
        flag=0;
        break;
    end
    s=path(s,v);
    pa(i)=s;
    i=i+1;
end

end
%===================================

%=============主函数==================
[C,B]=CB(n,tk);
f=zeros(n);
tm=C;tmb=B;

while 1
[pa,flag]=short(B,1,n);
disp(['path:' num2str(pa)]);
if flag==0
    disp('No path');
    break;
end

for i=1:length(pa)-1%得到新流
    xx=pa(i);yy=pa(i+1);
    if tm(xx,yy)~=0
      tt(i)=tm(xx,yy)-f(xx,yy);
    else
      tt(i)=tm(yy,xx);
    end   
end

for i=1:length(pa)-1
    xx=pa(i);yy=pa(i+1);
    if tm(xx,yy)~=0
       f(xx,yy)=f(xx,yy)+min(tt);
    else
       f(yy,xx)=f(yy,xx)-min(tt);
    end
end

ttb=B;
for uu=1:length(pa)-1 %得到新的赋权图
    i=pa(uu);j=pa(uu+1);
    if f(i,j)~=0  
    if f(i,j)<tm(i,j)
        C(i,j)=tm(i,j)-f(i,j);
    end
    if abs(f(i,j)-tm(i,j))<0.0001
        C(i,j)=0;
        B(i,j)=inf;
    end
    if f(i,j)>0
        C(j,i)=f(i,j);
        B(j,i)=-ttb(i,j);
    end
    end
end
end
max_flow=0;
for i=1:n
    for j=1:n
        if f(i,j)~=0
            max_flow=max_flow+f(i,j)*tmb(i,j);
        end
    end
end
Max_flow=max_flow;
F=f;

end

2。最短路
function[pa,flag]=short(B,s,v)   
%求最短路[pa,flag]=short(B,s,v)
%B为邻接距阵,s为起始点,v为终点
%pa返回最短路,有最短路flag为1,否则为0
% 例：
% B=[0 50 inf inf inf
%    inf 0 inf inf inf
%    inf 300 0 20 inf
%    inf inf inf 0 70
%    65 inf 100 inf 0];
% s=3;%起始点
% v=2;%终点
% [pa,flag]=short(B,s,v)

n=size(B,1);
D=B;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
%做n迭代,每次迭代均更新D(i,j)和path(i,j)
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
i=1;
pa(i)=s;
i=i+1;
flag=1;
while s~=v
    if path(s,v)==0
        flag=0;
        break;
    end
    s=path(s,v);
    pa(i)=s;
    i=i+1;
end
end

3。最小生成树
function [T,c]=tree_prim(a,n)
%Prim's algorithm O(n^2)
%最小生成树算法
% Example:
% n=6;
% a=[0 8 inf 1 5 4
%     8 0 6 inf 7 4
%     inf 6 0 9 10 4
%     1 inf 9 0 3 4
%     5 7 10 3 0  4
%     2 3 4 5 6 0];
% [T,c]=tree_prim(a,n);

T=[];c=0;v=1;***=2:n;
for j=2:n
    b(1,j-1)=1;
    b(2,j-1)=j;
    b(3,j-1)=a(1,j);
end

i=min(b(3,:));

while size(T,2)<n-1
    i=min(i,min(b(3,:)));
    T(:,size(T,2)+1)=b(:,i);
    c=c+b(3,i);
    v=b(2,i);
    temp=find(***==b(2,i));
    ***(temp)=[];b(:,i)=[];
    for j=1:length(***)
        d=a(v,b(2,j));
        if d<b(3,j)
            b(1,j)=v;b(3,j)=d;
        end
    end
end