djstl1.txt

matlab程序实现 最短路径问题 最短路径问题是图论研究中的一个经典算法问题

function [newTV,newlastPinChain,nowselP]=updateTP(lastselP,lastselPV,oldTC,oldTV,oldlastPinChain,n)

% 从最新的P标点出发更新T标值、各T标点上一节点标号并返回将进入P标集的T标点标号

% 输入：(6)

%        lastselP 最新P标点标号

%       lastselPV 最新P标点标值

%           oldTC 当前T标集

%           oldTV 当前T标值

% oldlastPinChain 节点的上一节点标号

%               n 节点总数

% 输出：(3)

%           newTV 更新后的T标值

% newlastPinChain 更新后的节点其上一节点标号

%         nowselP 即将进入P标集的T标点标号

    global bb

    No=1:n;                         % 节点编号序列

    TNo=No(oldTC);                  % T标号序列

    for tn=TNo                      % 逐一更新T标点的标值及其上一节点

        if (bb(lastselP,tn)>=0)&(bb(lastselP,tn)<Inf)&(lastselPV+bb(lastselP,tn)<oldTV(tn)) % P标点lastselP直达T标点tn且路程小于原T标值

            oldTV(tn)=lastselPV+bb(lastselP,tn);

            oldlastPinChain(tn)=lastselP;

        end

    end

    newTV=oldTV;newlastPinChain=oldlastPinChain;

    %%%%%%%%%%%%%%%%%

    ttV=Inf;nowselP=0;tNos=[];

    for tn=TNo

        if newTV(tn)<ttV

            ttV=newTV(tn);

            tNos=tn;

        else if newTV(tn)==ttV

                tNos=[tNos,tn];

            end

        end

    end

    m=length(tNos);

    nowselP=tNos(randint(1,1,[1,m]));

    %%%%%%%%%%%%%%%%%%%%%

%    ttV=Inf;nowselP=0;

%   for tn=TNo

%      if newTV(tn)<ttV

   %         ttV=newTV(tn);

    %        nowselP=tn;

    %   end

    %end

    

function [dist,chn]=getRetData(finalPC,finalPV,lastPinChain,sP,eP)

% 得到由起点sP到终点eP的最短路（路程、路径）

% 输入：(5)

%      finalPC P标集

%      finalPV P标值

% lastPinChain 各节点的上一节点标号

%           sP 起点标号

%           eP 终点标号

% 输出：(2)

%         dist 最短路程

%          chn 最短路径

    dist=finalPV(eP);chn=[];P=eP;

    while P~=sP

        chn=[chn,P];

        P=lastPinChain(P);

    end

    chn=[chn,sP];

    chn=backSort(chn);

    

function backarr=backSort(arr)

% 将序列arr倒序

    s=size(arr);n=s(1)*s(2);

    for k=1:n

        backarr(k)=arr(n-k+1);

    end