菜鸟的数学建模之路(一):最短路径算法「建议收藏」

菜鸟的数学建模之路(一):最短路径算法「建议收藏」最短路径算法主要有两种,Dijkstra算法和floyd算法,当时在学习这两种算法时经常弄混了,关于这两种算法,记得当时是在交警平台设置的那一道题目上了解到的,就去查很多资料,花了不少时间才基本了解了这两种算法的基本用法,在总结的时候,我更多的是用代码的方式去做的总结,当时想的是等到要用的时候,直接改一下数据,运行代码,得到想要的最短路径就可以了。记得我们老师说过数学建模的知识没必要过于深入的去学…

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

最短路径算法主要有两种,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

上面很多东西的整理都是来自网上一些博主,想具体深入学习的话可以多去网上搜一搜一些博主的博文。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136084.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • chmod- linux修改文件权限[通俗易懂]

    chmod- linux修改文件权限[通俗易懂]在Unix和Linux的各种操作系统下,每个文件(文件夹也被看作是文件)都按读、写、运行设定权限。例如我用ls-l命令列文件表时,得到如下输出:-rw-r–r–1appleusers22542006-05-2013:47tt.htm从第二个字符起rw-是说用户apple有读、写权,没有运行权,接着的r–表示用户组users只有读权限,没有运行权,最后的r–指其他人(others)只有读权限,没有写权和运行权。这是系统默认设置,我可以改写tt.htm,同组的人和其他

  • 平民版均线量化交易模型

    平民版均线量化交易模型前言2021年转瞬即逝,回顾一下在蚂蚁上定投的基金,在金融危机风雨欲来的2022年,分享一个懒人版的理财策略,愿大家新年里能财源广进,元旦快乐。基金定投我的策略非常简单,每月无脑小额定投,…

  • 【原创】ERROR 1142 (42000): command denied to user 引发的权限不足问题[亲测有效][通俗易懂]

    【原创】ERROR 1142 (42000): command denied to user 引发的权限不足问题[亲测有效][通俗易懂]mysqlgrants引发的权限不足问题[42000]基于mysql5.7.x1、先退出mysql,找到mysql的配置文件我的文件在这里./etc.my.cnf2、然后重新启动mysql,3、进入mysql,切换到mysql数据库,找到user表,查看user表的权限:4、修改权限,基于mysql5.7.x正常创建数据库查看权限>>>showgrants;…

  • python贪吃蛇编程代码大全_200行python代码实现贪吃蛇游戏

    python贪吃蛇编程代码大全_200行python代码实现贪吃蛇游戏本文实例为大家分享了python实现贪吃蛇游戏的具体代码,供大家参考,具体内容如下这次我们来写一个贪吃蛇游戏下面贴出具体代码importpygameimporttimeimportnumpyasnp#此模块包含游戏所需的常量frompygame.localsimport*#设置棋盘的长宽BOARDWIDTH=48BOARDHEIGHT=28#分数score=0cl…

  • ubuntu16.04 安装 Eric6「建议收藏」

    从安装qt,到安装qtpy,到安装Eric6,这是一个很痛苦的过程。总是会有一大段的错误,然后在网上各种搜索,然后去改,然后还是有新的错误,又去找答案,一直重复,我都快崩溃了。最后,终于,找到这一篇博客:http://blog.csdn.net/suxiang198/article/details/52042526。这篇博客解决了大部分坑,不过到后面部分还是出现了问题,安装不上去。最后,终于在E

  • SQL 配置管理器找不到了

    SQL 配置管理器找不到了想用数据库建立远程连接,于是想把数据库改成IP地址连接,突然发现配置管理器不见了!!!!???百度了一下,有人说可以用win+R打开后,输入SQLServerManager10.msc后确定,就可以找到了,大家可以试试,不知道为什么我的不行。于是,花了点时间找了一下,发现,点击计算机——>右键——>管理——>服务应用程序——>终于找到了。。。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号