Dijkstra算法例题代码

妳融我半世心霜

Dijkstra算法
function[dij , pij , nij]=minRoute()
    % 网络拓扑结构
    topo = [ 0,  20,  18,  18,  15, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf;
            20,   0,  26, inf,  28, inf, inf, inf,  30,  28,  30,  30, inf, inf, inf, inf, inf, inf;
            18,  26,   0,  20, inf, inf, inf, inf, inf, inf, inf,  20, inf,  26, inf, inf, inf, inf;
            18, inf,  20,   0,  18,  18,  50, inf, inf, inf, inf, inf, inf, inf, inf,  18, inf, inf;
            15,  18, inf,  18,   0, inf,  38,  32, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf;
           inf, inf, inf,  18, inf,   0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  36;
           inf, inf, inf,  50,  38, inf,   0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  34;
           inf, inf, inf, inf,  32, inf, inf,   0,  36, inf, inf, inf, inf, inf, inf, inf, inf, inf;
           inf,  30, inf, inf, inf, inf, inf, inf,   0, inf, inf, inf, inf, inf, inf, inf, inf, inf;
           inf,  28, inf, inf, inf, inf, inf, inf, inf,   0,  30, inf, inf, inf, inf, inf, inf, inf;
           inf,  30, inf, inf, inf, inf, inf, inf, inf,  30,   0,  26,  32, inf, inf, inf, inf, inf;
           inf,  30,  20, inf, inf, inf, inf, inf, inf, inf,  26,   0,  28, inf, inf, inf, inf, inf;
           inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  32,  28,   0,  32, inf, inf, inf, inf;
           inf, inf,  26, inf, inf, inf, inf, inf, inf, inf, inf, inf,  32,   0,  34, inf, inf, inf;
           inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  34,   0,  24,  36, inf;
           inf, inf, inf,  18, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  24,   0,  30, inf;
           inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,  36,  30,   0,  32;
           inf, inf, inf, inf, inf,  36,  34, inf, inf, inf, inf, inf, inf, inf, inf, inf,  32,   0;];
      
    dij = ones(size(topo)) * inf; % 距离矩阵
    pij = zeros(size(topo));      % 前一跳矩阵
    nodeNum = size(topo  , 1);

    for nodeI = 1 : nodeNum
        sourceNode = nodeI; % 源节点
        dij(sourceNode , sourceNode) = 0;   % 源节点到源节点的距离为0
        
        s = []; % 已计算节点集合
        q = 1 : nodeNum;    % 未处理节点集合
        qval = topo(sourceNode , ;    % 源节点到未处理节点的单挑距离
        
        while size(q , 2) > 0 % 对为处理的节点进行遍历
            [x , index] = sort(qval);   % 选择最近节点
            s(end+1) = q(1 , index(1)); % 加入已经处理节点集合
            u = q(1 , index(1));        % 获得当前处理节点的id
            for i = 1 : size(topo(u , , 2)
                if topo(u , i) < inf   % 考察u节点的所有直接连接节点
                    if dij(sourceNode , i) > dij(sourceNode , u) + topo(u , i)
                        % 如果源节点到u的距离加上u到i节点的距离要比源节点直接到i节点的距离近
                        % 则u应该出现在最短路径上 ， 跟新源节点到i节点的距离值
                        dij(sourceNode , i) = dij(sourceNode , u) + topo(u , i);
                        pij(sourceNode , i) = u;
                    end
                end
            end
            q(index(1)) = []; % 从q和qval集合中移除u节点
            % qval(index(1)) = []; % 没有更新待测节点的距离矩阵
            qval = dij(sourceNode , q); % 修正！！！
        end
    end

    % 将前一跳矩阵转换为下一跳矩阵
    for i = 1 : nodeNum
        for j = 1 : nodeNum
            s = [j];
            temp = j;
            if (pij(i , temp) > 0) % 10/11/2014修正
                while temp ~= i
                    s(end + 1) = pij(i , temp);
                    temp = pij(i , temp);
                end
                temp = i;
                for k = size(s , 2) - 1: -1 : 1
                    nij(temp , j) = s(1 , k);
                    temp = s(1 , k);
                    end
            end
        end
    end
end