dij.m

钢管订购和运输的最优规划 程序使用说明： 两种方法进行 1

function [C,LAMDA]=Dij(w)
C=ones(7,14)*Inf;
w1=w+w';
LAMDA=zeros(7,38);
for D=1:7
    T=ones(1,38)*Inf;
    P=zeros(1,38);
    lamda=zeros(1,38);
    S=zeros(1,38);
    k=D;
    S(D)=k;
    i=1;
    lamda(D)=-1;
    while(1)
        if(length(find(S==0))==0)%判断S是否都已经解决
            break;
         end
         Lsub=0;
         sub=0;
        sub=find(w1(k,:)~=0);%查找k行所有的相临的节点
        
        if(length(find(S(sub)==0))~=0)%对相临节点还没便历过的
        for j=1:length(sub)  %对每一个相临节点遍历，
            if(S(sub(j))==0)%只有没检查时才检查，如果已经检查过了就不检查
                if(sub(j)<25&k<25)%开始计算费用，判断当前节点与前一节点为铁路时，进行铁路运费的计算
                    Lsub(1)=sub(j);
                    Lsub(2)=k;
                    v=3;
                    ktemp=k;
                    while(lamda(ktemp)<25&lamda(ktemp)~=-1)%统计到不是铁路的节点为止
                         Lsub(v)=lamda(ktemp);
                         ktemp=Lsub(v);
                         v=v+1;
                    end
                    costsum=0;%记录路线中的铁路费用
                    for ii=1:length(Lsub)-1%所有的铁路段相加，求出铁路长度的总和
                      costsum=w1(Lsub(ii),Lsub(ii+1))+costsum;
                    end
                    costsum=traincost(costsum);%调用traincost求出铁路费
                    totalcost=costsum+P(Lsub(end));%记录从起点开始到这点的总费用
                 else
                    totalcost=P(k)+w1(k,sub(j));%如果是公路，只需要相加即可
                 end%end if sub
                 if(T(sub(j))>totalcost)%如果T标号中的对应点比求出的总费用大，则替换T标号中的内容
                     T(sub(j))=totalcost;
                     lamda(sub(j))=k;
                 end
             else
                subtemp(j)= 0;
           end%end if S
        end%end forj
        elseif(length(find(S(sub)==0))==0)%没有全部找到,没有完成解题的要求，但是相临的点都已经找到，那么用前一次的起点
            %k=karray(i-1);
            Sv=S(find(S~=0)); %得到S中所有不等于0，主要为了查找另一个起点
            flag=0;%找点的标志，0未找到点,1找到
            for Svi=1:length(Sv)%遍历每一个起点，查找还有可以继续进行计算的相临的点作为起点
                sub2=find(w1(Sv(Svi),:)~=0);%查找已经标号的点的相临的点。
                for sub2i=1:length(sub2)%看是否他的每一个相临点都已经找过了
                    ftemp=find(w1(sub2(sub2i),:)~=0);%相临点与哪些点相连
%                     isnotdian=;l&
                    if(length(find(S==sub2(sub2i)))==0&sub2(sub2i))%这里排除了一个顶点不在有延伸的点，且相连的一点以遍历
                        if(length(ftemp)~=1&ftemp~=Sv(Svi))
                           k=sub2(sub2i);       %最终在这里找到k点
                        		flag=1;
                        		break;  
                        end
                       
                    end
                end
                if(flag==1) %如果找到则跳出这个循环
                    break;
                end
            end
        end%end if length
      %  Tv=min(T(subtemp(find(subtemp~=0))));
      [Tv,Tvsub]=min(T);
%         if(Tv<Inf&length(find(subtemp~=0))~=0)
          if(Tv<Inf)
            T(Tvsub)=Inf;
            P(Tvsub)=Tv;%相应的最小值存入相应的P标号当中
            S(Tvsub)=Tvsub;%同时把这个找到的最小值的相临的点放入S中
            k=Tvsub;%把找到的相临的点作为下一个起始点
          elseif(length(find(S(sub)==0))==0)%没有全部找到,没有完成解题的要求，但是相临的点都已经找到，那么用前一次的起点
            %k=karray(i-1);
            Sv=S(find(S~=0)); %得到S中所有不等于0，主要为了查找另一个起点
            flag=0;%找点的标志，0未找到点,1找到
            for Svi=1:length(Sv)%遍历每一个起点，查找还有可以继续进行计算的相临的点作为起点
                sub2=find(w1(Sv(Svi),:)~=0);%查找已经标号的点的相临的点。
                for sub2i=1:length(sub2)%看是否他的每一个相临点都已经找过了
                    ftemp=find(w1(sub2(sub2i),:)~=0);%相临点与哪些点相连
%                     isnotdian=;l&
                    if(length(find(S==sub2(sub2i)))==0&sub2(sub2i))%这里排除了一个顶点不在有延伸的点，且相连的一点以遍历
                        if(length(ftemp)==1&ftemp==Sv(Svi))
                            continue;
                        end
                        k=sub2(sub2i);       %最终在这里找到k点
                        flag=1;
                        break;
                    end
                end
                if(flag==1) %如果找到则跳出这个循环
                    break;
                end
            end
        else
            break;% out while所有点都找到的时候就结束此问题的一个工厂起点的搜索
        end%end if Tv
        i=i+1;%i递增继续
    end%end while
    C(D,:)=P([25:38]);
%     lamdalength=size(lamda,2);
%     LAMDA(D,lamdalength)=0;
if(size(lamda,2)~=38)
    lamda(1,38)=0;
end 
    LAMDA(D,:)=lamda;
end%end for D