djstl.txt

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

function [distance,chain]=coDijkstra(startP,endP,right_noendP)

% 求非负权赋权图（附加非终点顶点固定权）的最短路程（路径）

% 输入：(3)

%     pMatrix 图的权矩阵

%      startP 起点标号

%        endP 终点标号

%right_noendP 非终点顶点固定权值(分量1：汽换汽；分量2：汽换铁；分量3：铁换铁；分量4：铁换汽） ~~~~~

% 输出：(2)

%    distance 最短路程值

%    chain 最短路径（标号序列）

    global bb

    n=size(bb,1);                     % 节点数

    TC=logical(ones(1,n));TV(1:n)=Inf; % TC为试探标号集，TV为试探标值

    PC=~TC;PV(1,n)=0;                   % PC为永久标号集，PV为永久标值

    lastPinChain=zeros(1,n); % lastPinChain记录了各节点在最短路径中的上一个节点编号

    distance=Inf;chain=[];

    % ---- 初始化：让节点startP成为第一个永久节点,标值为0；startP为最新产生的P标点 ----

    PC(startP)=true;TC=~PC;selP=startP;

    % ------------ 循环扩展P点集 -------------

    while selP~=endP      % 当最新成为P节点的T节点为终点时循环结束

        [TV,lastPinChain,selP]=updateTP(selP,PV(selP),TC,TV,lastPinChain,n); % 更新T标值、各T标点上一节点标号并返回值最小T标号

        if selP==0

            return

        end

        %%~~~~~~~~~~~~~~~ 换乘支付 ~~~~~~~~~~~~~~~~~~

        if selP~=endP   % 没到终点（换乘）

            if lastPinChain(selP)<=3957   % 由汽换乘

                if selP<=3957 % 汽换汽

                    TV(selP)=TV(selP)+right_noendP(1);

                else          % 汽换铁

                    TV(selP)=TV(selP)+right_noendP(2);

                end

            else                    % 由铁换乘

                if selP>3957 % 铁换铁

                    TV(selP)=TV(selP)+right_noendP(3);

                else          % 铁换汽

                    TV(selP)=TV(selP)+right_noendP(4);

                end

            end

        end

        %%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

        PC(selP)=true;PV(selP)=TV(selP);    % 更新P标集、P标值

        TC=~PC;                             % 更新T标集

    end

    % ----------- 组织返回的最短路径和最短路程值 ------------

    [distance,chain]=getRetData(PC,PV,lastPinChain,startP,endP);

    % -------------------------------------------------------