MATLAB实现Dijkstra算法教程‌

% 功能:     实现改良的Dijkstra算法
% 修改时间:  初版2021-8-30 20：00,修改于2022-10-25 22:35
% 编写人：   湖北工业大学.机械工程学院.力创团队.人工智能部.黄沛鑫
% 版权声明:  如需转载，请务必标明出处
function op=dijkstra2(W,startsite,pausesite)
    % 说明：
    %     1. 函数输出为行向量op，op记录着两个目标点的最短路径
    %     2. 函数名为dijkstra2
    %     3. 函数输入变量有三个。W是赋权图的邻接矩阵，startsite是起点，pausesite是终点；
    % step1：读取邻接矩阵的大小
        [m1,~] = size(W); % 邻接矩阵是方阵，所以大小是m1*m1的矩阵
    % step2： 如果起始点不是邻接矩阵的首个点，需要将邻接矩阵转变一下
        if startsite ~= 1 %%%
            W([1 startsite],:) = W([startsite 1],:); % 交换行
            W(:,[1 startsite]) = W(:,[startsite 1]); % 交换列
        end
    % step3： 初始化
        s = zeros(1, m1);               % s向量 用来储存起点到各个点的最短路径的值
        fathersite = zeros(1, m1);      % fathersite向量 用来储存对应点的父点
                                        % 注：父点解释
                                        %    假设从1号点到6号点的路径为1->3->5->7->6
                                        %    那么 6 的父点是 7，7的父点是5.
                                        %    这里使用父点这个概念，用以帮助路径的表达
        t = zeros(1, m1);               % t向量 用来储存起点到各个点的可能的最短路径的值
        for i = 1:m1
            t(i) = nan;                 % 将t中元素的值进行处理，方便后面进行工作。后面将会在t中，挑出某一次迭代中，路径值最小的点，然后再进行处理。
        end
        num = 1:m1;                     % num向量 是一个从1到m1，步进为1的向量。用来记录对应点是否已经找到最短路径。若是找到了，那么后面将会对应作出处理
        newsite = 1;                    % newsite是用来记录最新的，已经被确认下来的，找到到起点的最短路径的解的点
    % step4： 主要迭代
        s (1) = 0;                      % 将起点到起点的距离设置为0
        for i=1:1:10000000000000000     % 这个循环通过迭代不断更新数据
            for j = num                 % 历遍
                if j == 0               % 必要性判断
                    continue
                end
                if W(newsite, j) ~= inf
                    c = W (newsite, j)+s (newsite);
                    if isnan (t(j)) || c < t(j)
                        t(j) = c;
                        fathersite(j)= newsite;
                    end
                end
            end
            newsite = find (t == min (t));
            s (newsite) = min (t);
            num (newsite) = 0;           % 与必要性判断呼应
            t (newsite) = nan;
            if sum(num)==0
                break;
            end                 % 如果所有的t全是nan值的话，意味着最短路径已经找到，停止迭代。
        end
    % step5： 进行step2的逆变换
        for i=1:m1 % 将起点的值换为编号，将一号点的值换为编号
            if fathersite(i)==1
                fathersite(i)=startsite;
            elseif fathersite(i)==startsite
                fathersite(i)=1;
            else
                HBUThpx=0; % 无用步骤
            end
        end
        io=fathersite(1);
        fathersite(1)=fathersite(startsite);
        fathersite(startsite)=io;%这里我们将结果中的起点和1号点换个位置。因为一开始，我们将邻接矩阵的第一列和第一行换成了起点
        po=fathersite(pausesite);
        op=[po,pausesite];
        for i=1:m1 % 历遍，更新储存路径值
            if po~=1
                po=fathersite(po);% 通过每个点的父点溯回路径
                op=[po,op];
            else
                break;%当路径点寻找到了1号点，结束循环
            end
        end
    % step6： 结果优化
        line=[];
        for i=1:length(op)
            if i==1
                line=[line,op(i)];
            else
                if op(i)==op(i-1)
                    continue;
                end
                line=[line,op(i)];
            end
        end
        op=line;
end

%测试数据
clc;clear;
weight1=[0   2   1   8   inf inf inf inf
        2   0   inf 6   1   inf inf inf
        1   inf 0   7   inf inf 9   inf
        8   6   7   0   5   1   2   inf
        inf 1   inf 5   0   3   inf 9
        inf inf inf 1   3   0   4   6
        inf inf 9   2   inf 4   0   3
        inf inf inf inf 9   6   3   0];
startsite1=1;
pausesite1=5;
op1=dijkstra2(weight1,startsite1,pausesite1);
disp([num2str(startsite1),'号点到',num2str(pausesite1),'号点的路径是',num2str(op1)]);
%
weight2=[0  1   12  inf inf inf
        inf 0   9   3   inf inf
        inf inf 0   inf 5   inf
        inf inf 4   0   13  15
        inf inf inf inf 0   4
        inf inf inf inf inf 0];
startsite2=2;
pausesite2=6;
op2=dijkstra2(weight2,startsite2,pausesite2);
disp([num2str(startsite2),'号点到',num2str(pausesite2),'号点的路径是',num2str(op2)]);

1号点到5号点的路径是1  2  5
2号点到6号点的路径是2  4  3  5  6