菜鸟的数学建模之路（一）：最短路径算法「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

最短路径算法主要有两种，Dijkstra算法和floyd算法，当时在学习这两种算法时经常弄混了，关于这两种算法，记得当时是在交警平台设置的那一道题目上了解到的，就去查很多资料，花了不少时间才基本了解了这两种算法的基本用法，在总结的时候，我更多的是用代码的方式去做的总结，当时想的是等到要用的时候，直接改一下数据，运行代码，得到想要的最短路径就可以了。记得我们老师说过数学建模的知识没必要过于深入的去学习，只要在要用的时候，能想起有这个知识存在，知道大概是用来干嘛，并且能拿过来用就行了（大概就是这个意思）。

这里分享一下个人觉得最快效率学习数学建模的方法，因为数学建模涉及的知识点太多太多，不可能每一个都深入的学习，为了能达到高效的学习，我是把很多知识点当成一个工具来用，把知识点基本学一遍，知道是用来干嘛的，并且在需要的时候可以拿过来用，只需要改个数据就好了。为了能达到这个目的，很多时候我都是通过案例，保存源代码，解读源代码，做好自己能看得懂的注释，再改一下代码，等到要用的时候就改个数据，运行代码就可以用了，感觉这样的学习效率还是挺高的。下面的很多总结基本都是这样的思路写出来的。

Dijkstra算法

关于Dijkstra算法的定义这里就不写了，总之一句话就是求一个源点到其他各顶点的最短路径，想要具体知道更加详细的介绍的话可以看看以下其他博主的博文或自己百度：
https://blog.csdn.net/qq_39521554/article/details/79333690
https://blog.csdn.net/capoziom/article/details/81866346

下面直接给案例，主要是matlab代码的解释：
建议先看上面第二条链接的博文（https://blog.csdn.net/capoziom/article/details/81866346）不然看不懂下面的内容
在这里插入图片描述
（1）结点个数n；
（2）二维矩阵M（nxn），距离矩阵，连通的结点间即为距离，不连通的结点间为正无穷，和自己的距离为0；
（3）一维矩阵pb（1xn），若第i点已找到最短路径，则pb（i）=1，否则等于0，对于初始结点，pb=1；
（4）距离矩阵d（1xn），若第i点已找到最短路径，则的d（i）=最短距离，否则为0，初始结点d=0；
（5）上一结点矩阵path（1xn)，若第i点找到了最短路径，则path存放这一条最短路径的前一个结点，通过对每一点的回溯，可以找到最短路径。

上面只是代码的初始化，最终经过下面代码运行，得到最终的最短路径及其相关的路径信息。

先看上面第二条链接的博文才能知道这些变量的含义

代码：

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
%Dijkstra算法介绍：求一个源点到其他各顶点的最短路径
%               
% 变量设置
% （1） 结点个数n； 
% （2）二维矩阵M（nxn），距离矩阵，连通的结点间即为距离，不连通的结点间为正无穷，和自己的距离为0； 
% （3）一维矩阵pb（1xn），若第i点已找到最短路径，则pb（i）=1，否则等于0，对于初始结点，pb=1； 
% （4）距离矩阵d（1xn），若第i点已找到最短路径，则的d（i）=最短距离，否则为0，初始结点d=0； 
% （5）上一结点矩阵path（1xn)，若第i点找到了最短路径，则path存放这一条最短路径的前一个结点，通过对每一点的回溯，可以找到最短路径。

% 方法说明：
% size(a)表示矩阵每个维度的长度，即几行几列（size([1 2 3;4 5 6]) = [2,3]）
% length(a)表示矩阵a的最大的长度，即max(size(a)),length([1 2 3;4 5 6])等于3，因为2和3中最大是3
% Inf表示无穷大
% find（条件）表示找到符合条件的元素的下标，返回下标的集合
% 
% 该函数使用方法：
% 输入：要求的最短距离的矩阵，下例矩阵为m
% 输出：d:起点到任何点的最短路径的距离集合
%       path:存放这一条最短路径的前一个结点的集合，通过回溯可得到最短的具体路径
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 




clc;clear;
%定义n阶零矩阵
m = [0,6,Inf,Inf,Inf,2;
    6,0,2,Inf,Inf,1;
    Inf,2,0,4,1,5;
    Inf,Inf,4,0,1,Inf;
    Inf,Inf,1,1,0,7;
    2,1,5,Inf,7,0];

n=6;   %设置矩阵大小
temp=1;  %设置起始点

pb(1:length(m))=0;pb(temp)=1;%求出最短路径的点为1，未求出的为0
% 或者pb = [1,0,0,0,0,0];

d(1:length(m))=0;%存放各点的最短距离
% 或者d = [0,0,0,0,0,0];

path(1:length(m))=0;%存放各点最短路径的上一点标号
% 或者path = [0,0,0,0,0,0];

while sum(pb)<n %判断每一点是否都已找到最短路径
 tb=find(pb==0);%找到还未找到最短路径的点
 fb=find(pb);%找出已找到最短路径的点
 min=inf;
 for i=1:length(fb)
     for j=1:length(tb)
         plus=d(fb(i))+m(fb(i),tb(j));  %比较已确定的点与其相邻未确定点的距离
         if((d(fb(i))+m(fb(i),tb(j)))<min)
             min=d(fb(i))+m(fb(i),tb(j));
             lastpoint=fb(i);
             newpoint=tb(j);
         end
     end
 end
 d(newpoint)=min;
 pb(newpoint)=1;
 path(newpoint)=lastpoint; %最小值时的与之连接点
end
fprintf('距离矩阵：%d');
m

fprintf('已找到最短路径的点的集合');
pb

fprintf('已找到最短路径的总距离');
d

fprintf('已找到最短路径的距离（往前回溯）');
path

运行结果：

从结果来看，v1到v1最短距离：0；v1到v2最短距离：3；v1到v3最短距离：5；…
关于最短距离的回溯（有的博主没有解释，这里给出个人的理解）：

v1到其他顶点的路径，有感兴趣的可以在评论区通过回溯的方式列出来。

floyd算法

floyd算法介绍：求任意一对顶点之间的最短路径
关于floyd算法，建议看一下以下博主的文章：
https://blog.csdn.net/kabuto_hui/article/details/82886826
个人看了觉得挺好的

下面的代码也是里面的案例：

求v1到v4各个顶点间的最短距离，

matlab求解代码：

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
% %floyd算法介绍：求任意一对顶点之间的最短路径
% %               
% % 变量设置
% % （1） 结点个数n； 
% % （2）一个距离矩阵d:用于存储各顶点之间的距离
% % （3）一个路由矩阵r：存储各顶点的路径，用于最终路径的寻找
% % 
% % 方法说明：
% % Inf表示无穷大
% % 
% % 该函数使用方法：
% % 输入：距离矩阵d，一个路由矩阵r
% % 输出：d:任意顶点之间的最短路径的距离集合
% %       r:最终路径的点的集合
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %




clc
d = [0,2,6,4;
    Inf,0,3,Inf;
    7,Inf,0,1;
    5,Inf,12,0];

r = [1,2,3,4;
    1,2,3,4;
    1,2,3,4;
    1,2,3,4];
n = length(d);

%floyd算法，结果为d和r
for k=1:n
    for i=1:n
        for j=1:n
            if d(i,k)+d(k,j)<d(i,j)
                d(i,j)=d(i,k)+d(k,j);
                r(i,j)=r(i,k);
            end 
        end 
    end
end
fprintf('各个顶点之间的最短距离：');
d
fprintf('路由矩阵：');
r
fprintf('--------------------路径打印-----------------------\n');
% 路径的打印
for i = 1 : n
  for j = 1 : n
    start = i;
    dest = j;
    while 1
         if(r(start, dest)  ~= dest)
             fprintf('V%s -> ', num2str(start));
             start = r(start, dest);
         else
             fprintf('V%s -> ', num2str(start));
             fprintf('V%s\n', num2str(dest));
             break;
         end
    end
  end
end

运行截图：

d表示各个顶点之间的最短距离：
V1 -> V1：0
V1 -> V2：2
V1 -> V2 -> V3：5
V1 -> V4：4
V2 -> V3 -> V4 -> V1：9
V2 -> V2：0
V2 -> V3：3
V2 -> V3 -> V4：2
…