精华内容
下载资源
问答
  • matlab解决最短路径问题

    千次阅读 2019-08-23 10:04:55
    这次主要是提供一个解决最短路径问题matlab app。 本次分享的最短路径问题app仅针对无向图,实际上由于单行道存在,很多时候实际问题是一个有向图,有向图内容我们将在后期介绍。 两种表示方法 邻接矩阵法...

    写在前面

    最短路径问题是图论研究中的一个经典算法问题。
    它旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

    这次主要是提供一个解决最短路径问题的matlab app。

    本次分享的最短路径问题app仅针对无向图,实际上由于单行道存在,很多时候实际问题是一个有向图,有向图内容我们将在后期介绍。
    最短路径问题示意图

    两种表示方法

    邻接矩阵法和邻接表法。

    邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

    邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称。

    这里我们用的是无向图的邻接矩阵表示图1中的地点和道路关系。例如地点1和地点2之间距离为6,则表1中矩阵1行2列和2行1列的值均为6,地点1和4之间没有道路,其矩阵表示为无穷大Inf。地点1与其自身距离为0。

    在这里插入图片描述
    邻接表只存储图中存在的边以及边的长度,例如点1和点2之间存在长度为6的边,那么邻接表中存在一行1,2,6。
    在这里插入图片描述

    minpath的安装

    在matlab当前路径下,双击minpath.mlappinstall即可完成安装。

    安装后的程序可以APP下面找到——
    在这里插入图片描述

    minpath的使用

    minpath支持邻接矩阵以及邻接表两种表示无向图的方式,支持读取存储在.mat文件、文本文件以及excel文件的数据,也支持手动输入数据。文本文件和excel文件可以选择添加一行表头。

    以下动图为minpath使用的操作实例。我们在testdata文件夹中提供了各种格式的测试数据。

    在这里插入图片描述
    在这里插入图片描述

    获取源代码或想要了解更多,欢迎关注公众号:数学建模公会
    在这里插入图片描述

    展开全文
  • MATLAB实现最短路径问题中的Floyd算法、代码以及说明文档。

    本文将说明最短路径问题中的Floyd算法原理,以及如何用MATLAB实现。

    正文

    在这里插入图片描述
    在这幅图中,如果我想知道任意两个点之间的最短距离,有什么好的办法吗?Floyd算法了解一下。

    在这个问题中,相邻两个点是“单向”的,也就是说从某点(就取名A点吧)到某点(就取名B点吧)的距离,和从B点到A点的距离不一定相等。Floyd算法可以用来解决这样的单向问题。当然,还有“双向”问题,及相邻两地的距离是固定的,无论出发地是哪个。双向问题显然是单向问题的特例,然而有的算法只能解决双向问题,因此在这里表扬一下Floyd的普适性。

    如果我们要从A点到B点,却被禁止中途经过任何其他的点作为中转站的话,我们就只好从A点直接走向B点了。这种情况下的两地最短距离是显而易见的——就是它俩的直接距离嘛。我们规定一下,如果A地点和B地点不相邻的话,那么它俩的直接距离就是无穷大。还有,A点到A点的直接距离是0。

    然后我们就可以画一个表格(其实就是之后要用代码建立的矩阵)。就一开始说的这个图而言,我们可以画出如下的表格(表中行号和列号都代表地点的编号。
    )。

    表格1:
    在这里插入图片描述
    表格中的数字就是两地的直接距离。例如3地点到4地点的直接距离是1。另外,按照我们的规定,1地点和1地点的距离是0,1地点和2地点由于不相邻,所以它俩直接距离是无穷。

    这个表格的含义是,在要求不经过任何中转站的条件下,两地之间的最短距离。由于是单向问题,我们规定两地距离是行编号所代表的地点—>列编号所代表的地点。

    用MATLAB生成这个表格(矩阵):
    e = [0,2,6,4;Inf,0,3,Inf;7,Inf,0,1;5,Inf,12,0];

    现在增加一个条件,中途最多只能经过1地点作为中转站。在这个条件下,有些地点之间的最短距离就会发生变化。例如,4地点到2地点的最短距离从无穷变成了9,或者是4地点到3地点,最短距离从无穷变成了11。于是我们又可以画出一个新的表。

    表格2:
    在这里插入图片描述
    这个表的含义是,在只允许经过1地点的条件下,两地之间的最短距离。可以发现我们一开始画的表格中的一些数字被更新了。

    那怎么用代码遍历任意的两点,查看在上述条件下它俩之间的最短距离是否有所更新?以下是代码。

    %i表示表格中第i行,j表示第j列
    %设一共有n个地点
    for i = 1:n %从第一行开始遍历到最后一行
        for j = 1:n %遍历到了某一行后,开始遍历列,从第一列开始遍历到最后一列
            if (e(i,j) > e(i,1) + e(1,j)) 
                e(i,j) = e(i,1) + e(1,j);  %如果i地和j地间通过1地点中转的话距离更近,就将该距离更新为这两地间最短距离
            end
        end
    end
    

    现在,如果在允许通过1地点作为中转的条件下,还允许把2地点也作为中转站,试问现在的最短距离?

    由于表格2已经蕴含了“允许通过1地点作为中转”的条件了,因此对于附加的这个条件,我们只需在表格2的基础上再进行遍历操作就可以,思想和之前的一样。

    以下是代码:

    %i表示表格中第i行,j表示第j列
    % 下面出现的e代表的是第二个表格
    for i = 1:n %从第一行开始遍历到最后一行
        for j = 1:n %遍历到了某一行后,开始遍历列,从第一列开始遍历到最后一列
            if (e(i,j) > e(i,2) + e(2,j))  %如果i地和j地间通过2地点中转的话距离更近,就将该距离更新为这两地间最短距离
                e(i,j) = e(i,2) + e(2,j);   %可以注意到,除了此处,其他部分代码完全一样!
            end
        end
    end
    

    然后我们就获得了第三个表格。

    表格3:
    在这里插入图片描述
    这里(1,3)和(4,3)中的元素作了更新,说明这两地间在允许把1地点作为中转站的基础上,因为再允许添加一个2地点作为中转站而进一步缩短了最短距离。

    按照这个思路下去,我们可以逐次增加沿途允许中转的地点,直到囊括所有地点——那岂不就是我们一开始想要解决的问题:在无任何约束下,求两地之间最短距离?

    十分好理解对吧。以下就是囊括所有中转站后的代码:

    for r = 1:n  %逐个增加中转站,增加n次
        for i = 1:n
            for j = 1:n
                if (e(i,j) > e(i,r) + e(r,j))
                    e(i,j) = e(i,r) + e(r,j);
                end
            end
        end
    end
    

    最终的结果如下:
    在这里插入图片描述

    迭代完成后,通过表格,任何两地之间的最短距离,我们都可以一目了然。这么好的算法不妨将其生成一个函数吧,方便日后调用:

    function [y]=floyd(n,e)
    %n 代表 矩阵阶数
    %e 代表 初始矩阵
    %y 代表 最终矩阵
    %----------------------------------------------
    for r = 1:n  %逐个增加中转站,增加n次
        for i = 1:n
            for j = 1:n
                if (e(i,j) > e(i,r) + e(r,j))
                    e(i,j) = e(i,r) + e(r,j);
                end
            end
        end
    end
    

    综上可见,Floyd算法的精髓在于,从一开始不允许走任何的中转地,到慢慢的增加中转地的数量,一步一步的缩短两地之间的最短距离,当允许将所有区域都作为中转地时,我们就达到了目的——即在没有任何约束条件下求两地最短距离!

    看到这,相信你已经理解Floyd算法的内核了,也知道了如何用MATLAB实现Floyd算法,并求得最短距离。如果你不必知道最短距离对应的路线,阅读可以到此结束。如果希望进一步获知最短路线到底是什么,请再看下文。

    最短路线获取

    那如果我们不仅要得到两地之间的最短距离,还想知道对应的最短路线呢?下面我们要对Floyd函数进行小小的改进。

    请看代码:

    function [e,v]=floyd_plus(n,e,A,B)
    %该函数不仅可以用于求最短距离,还可以得到最短距离对应的路径
    %n 代表 矩阵阶数
    %e 代表 初始矩阵
    %y 代表 最终矩阵
    %A 代表 出发地编号
    %B 代表 目的地编号
    %----------------------------------------------
    v = []; #用于存储中转站编号
    P = zeros(n); %P的作用不太好言简意赅地解释清,应该可以看懂
    for r = 1:n  %逐个增加中转站(r为新增的中转站的编号),增加n次
        for i = 1:n
            for j = 1:n
                if (e(i,j) > e(i,r) + e(r,j))
                    e(i,j) = e(i,r) + e(r,j);
                    P(i,j) = r;  %将该中转站的编号记录到对应位置
                end
            end
        end
    end
    
    k = B;
    while P(A,k) ~= 0
        v = [v,k];
        k = P(A,k); 
    end
    v = [v,[k,A]];
    v = v(end:-1:1); %倒序,让起点作为第一个元素,终点作为最后一个元素
    
    

    这是一个强大的算法,在地点达到数十个的时候尤其有用(再多的话写初始矩阵要把手写残了哈哈)下面附上一个该算法的应用,深深的体会Floyd算法的强大吧!
    进入后请看第二次作业的题目一和题目二

    参考文献

    1. Floyd-傻子也能看懂的弗洛伊德算法
    2. 已经找到了最短路径长度,但不知道如何输出最短路径所经过的顶点出来!
    展开全文
  • 本文将说明最短路径问题中的Floyd算法原理,以及如何用MATLAB实现。正文在这幅图,如果我想知道任意两个点之间的最短距离,有什么好的办法吗?Floyd算法了解一下。在这个问题,相邻两个点是“单向”的,也就是说...

    本文将说明最短路径问题中的Floyd算法原理,以及如何用MATLAB实现。

    正文

    dc20dd3776a44104a9b0de3ec598f86d.png

    在这幅图中,如果我想知道任意两个点之间的最短距离,有什么好的办法吗?Floyd算法了解一下。

    在这个问题中,相邻两个点是“单向”的,也就是说从A点到B点的距离,和从B点到A点的距离不一定相等。Floyd算法可以用来解决这样的单向问题。当然,还有“双向”问题,及相邻两地的距离是固定的,无论出发地是哪个。双向问题显然是单向问题的特例,然而有的算法只能解决双向问题,因此在这里表扬一下Floyd的普适性。

    如果我们要从A点到B点,却被禁止中途经过任何其他的点作为中转站的话,我们就只好从A点直接走向B点了。这种情况下的两地最短距离是显而易见的——就是它俩的直接距离嘛。我们规定一下,如果A地点和B地点不相邻的话,那么它俩的直接距离就是无穷大。还有,A点到A点的直接距离是0。

    然后我们就可以画一个表格(其实就是之后要用代码建立的矩阵)。就一开始说的这个图而言,我们可以画出如下的表格(表中行号和列号都代表地点的编号。

    )。

    表格1:

    3663af1d552b3975c61f28b2fbce2bf6.png

    表格中的数字就是两地的直接距离。例如3地点到4地点的直接距离是1。另外,按照我们的规定,1地点和1地点的距离是0,1地点和2地点由于不相邻,所以它俩直接距离是无穷。

    这个表格的含义是,在要求不经过任何中转站的条件下,两地之间的最短距离。由于是单向问题,我们规定两地距离是行编号所代表的地点—>列编号所代表的地点。

    用MATLAB生成这个表格(矩阵):

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

    现在增加一个条件,中途最多只能经过1地点作为中转站。在这个条件下,有些地点之间的最短距离就会发生变化。例如,4地点到2地点的最短距离从无穷变成了9,或者是4地点到3地点,最短距离从无穷变成了11。于是我们又可以画出一个新的表。

    表格2:

    8dad97b92dbad190e4f284ccb373caa6.png

    这个表的含义是,在只允许经过1地点的条件下,两地之间的最短距离。可以发现我们一开始画的表格中的一些数字被更新了。

    那怎么用代码遍历任意的两点,查看在上述条件下它俩之间的最短距离是否有所更新?以下是代码。

    %i表示表格中第i行,j表示第j列

    %设一共有n个地点

    for i = 1:n %从第一行开始遍历到最后一行

    for j = 1:n %遍历到了某一行后,开始遍历列,从第一列开始遍历到最后一列

    if (e(i,j) > e(i,1) + e(1,j))

    e(i,j) = e(i,1) + e(1,j); %如果i地和j地间通过1地点中转的话距离更近,就将该距离更新为这两地间最短距离

    end

    end

    end

    现在,如果在允许通过1地点作为中转的条件下,还允许把2地点也作为中转站,试问现在的最短距离?

    由于表格2已经蕴含了“允许通过1地点作为中转”的条件了,因此对于附加的这个条件,我们只需在表格2的基础上再进行遍历操作就可以,思想和之前的一样。

    以下是代码:

    %i表示表格中第i行,j表示第j列

    % 下面出现的e代表的是第二个表格

    for i = 1:n %从第一行开始遍历到最后一行

    for j = 1:n %遍历到了某一行后,开始遍历列,从第一列开始遍历到最后一列

    if (e(i,j) > e(i,2) + e(2,j)) %如果i地和j地间通过2地点中转的话距离更近,就将该距离更新为这两地间最短距离

    e(i,j) = e(i,2) + e(2,j); %可以注意到,除了此处,其他部分代码完全一样!

    end

    end

    end

    然后我们就获得了第三个表格。

    表格3:

    5b3c097e96673dd13f2b7874f8062455.png

    这里(1,3)和(4,3)中的元素作了更新,说明这两地间在允许把1地点作为中转站的基础上,因为再允许添加一个2地点作为中转站而进一步缩短了最短距离。

    按照这个思路下去,我们可以逐次增加沿途允许中转的地点,直到囊括所有地点——那岂不就是我们一开始想要解决的问题:在无任何约束下,求两地之间最短距离?

    十分好理解对吧。以下就是囊括所有中转站后的代码:

    for r = 1:n %逐个增加中转站,增加n次

    for i = 1:n

    for j = 1:n

    if (e(i,j) > e(i,r) + e(r,j))

    e(i,j) = e(i,r) + e(r,j);

    end

    end

    end

    end

    最终的结果如下:

    805caad1f64d7c3649fb2f6641b47ccb.png

    迭代完成后,通过表格,任何两地之间的最短距离,我们都可以一目了然。这么好的算法不妨将其生成一个函数吧,方便日后调用:

    function [y]=floyd(n,e)

    %n 代表 矩阵阶数

    %e 代表 初始矩阵

    %y 代表 最终矩阵

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

    for r = 1:n %逐个增加中转站,增加n次

    for i = 1:n

    for j = 1:n

    if (e(i,j) > e(i,r) + e(r,j))

    e(i,j) = e(i,r) + e(r,j);

    end

    end

    end

    end

    综上可见,Floyd算法的精髓在于,从一开始不允许走任何的中转地,到慢慢的增加中转地的数量,一步一步的缩短两地之间的最短距离,当允许将所有区域都作为中转地时,我们就达到了目的——即在没有任何约束条件下求两地最短距离!

    看到这,相信你已经理解Floyd算法的内核了,也知道了如何用MATLAB实现Floyd算法,并求得最短距离。如果你不必知道最短距离对应的路线,阅读可以到此结束。如果希望进一步获知最短路线到底是什么,请再看下文。

    最短路线获取

    那如果我们不仅要得到两地之间的最短距离,还想知道对应的最短路线呢?下面我们要对Floyd函数进行小小的改进。

    请看代码:

    function [e,v]=floyd_plus(n,e,A,B)

    %该函数不仅可以用于求最短距离,还可以得到最短距离对应的路径

    %n 代表 矩阵阶数

    %e 代表 初始矩阵

    %y 代表 最终矩阵

    %A 代表 出发地编号

    %B 代表 目的地编号

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

    v = []; #用于存储中转站编号

    P = zeros(n); %P的作用不太好言简意赅地解释清,应该可以看懂

    for r = 1:n %逐个增加中转站(r为新增的中转站的编号),增加n次

    for i = 1:n

    for j = 1:n

    if (e(i,j) > e(i,r) + e(r,j))

    e(i,j) = e(i,r) + e(r,j);

    P(i,j) = r; %将该中转站的编号记录到对应位置

    end

    end

    end

    end

    k = B;

    while P(A,k) ~= 0

    v = [v,k];

    k = P(A,k);

    end

    v = [v,[k,A]];

    v = v(end:-1:1); %倒序,让起点作为第一个元素,终点作为最后一个元素

    这是一个强大的算法,在地点达到数十个的时候尤其有用(再多的话写初始矩阵要把手写残了哈哈)下面附上一个该算法的应用,深深的体会Floyd算法的强大吧!

    进入后请看第二次作业的题目一和题目二

    参考文献

    Floyd-傻子也能看懂的弗洛伊德算法

    已经找到了最短路径长度,但不知道如何输出最短路径所经过的顶点出来!

    展开全文
  • 基于MATLAB最短路径SPFA算法 前面已述 对应单一源点到各顶点的最短路径算法 贝尔曼-福特和迪杰斯拉特算法 现在说明一下SPFA算法精髓: 在之前的Bellman-Ford算法存在一个重复更新的问题,即每个枢纽点都要对全部...

    基于MATLAB的最短路径SPFA算法
    前面已述 对应单一源点到各顶点的最短路径算法 贝尔曼-福特和迪杰斯拉特算法
    现在说明一下SPFA算法精髓:
    在之前的Bellman-Ford算法中存在一个重复更新的问题,即每个枢纽点都要对全部顶点更新计算
    SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间
    该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点

    现通过MATLAB软件阐述算法程序和运行结果
    算法说明
    算法程序
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    最终运行结果

    展开全文
  • 后人在它的基础上解决最短路径问题,也就是我们的邮递员问题,为了解决此问题,创建Dijkstra算法解决了从定点x0到目标点的最短路径问题。在学习matlab的过程,还得学学python,对于提高自己的编程能力有很好的锻炼...
  • 后人在它的基础上解决最短路径问题,也就是我们的邮递员问题,为了解决此问题,创建Dijkstra算法解决了从定点x0到目标点的最短路径问题。在学习matlab的过程,还得学学python,对于提高自己的编程能力有很好的锻炼...
  • [DIST,PATH,PRED] = graphshortestpath(G,S)确定从节点S到图G所有其他节点的单个源最短路径。边的权重是n-by-n邻接矩阵表示的所有非零条目通过稀疏矩阵G. [DIST,PATH,PRED] = graphshortestpath(G,S,...
  • graphshortestpath 函数是用来解决最短路径问题的。 语法为:  [dist, path, pred]=graphshortestpath(G,S) [dist, path, pred]=graphshortestpath(G,S,T)  G是稀疏矩阵,S是起点,T是终点。dist表示最短距离...
  • 利用 Matlab 编程计算最短路径位点选址,最短路问题 两个指定顶点之间的最短路径
  • MATLAB无向图 无权重w G1 = graph(s1,t1) ; plot (G1) %注意哦,编号最好是从1开始连续编号,不要自己随便定义编号 s1 = [1,2,3,4]; t1 = [2,3,1,1]; G1 = graph(s1,t1) ; plot(G1) %注意字符串元胞数组是用大...
  • 文章目录一、最短路径问题和算法的类型二、Dijkstra 算法三、采用 graphshortestpath 最短路径函数 一、最短路径问题和算法的类型 按路径长度的不同定义可将最短路径问题分为两大类:普通路径长度和一般路径长度。后...
  • MATLAB手动实现DQN最短路径问题

    千次阅读 2020-05-22 22:51:41
    不用强化学习工具箱的DQN算法案例与matlab代码 本文建立在已经有DQN基础知识之上。 案例说明: 环境设置:这是一个30*30的矩阵迷宫,其中有两个状态obstacle(15,15),Goal(25,25),目标就是Agent如何不碰到障碍物可以...
  • MATLAB-K最短路径算法(KSP,K-shortest pathes)

    千次阅读 热门讨论 2020-10-16 17:30:12
    1959 年,霍夫曼(Hoffman) 和帕夫雷(Pavley)在论文第一次提出k 最短路径问题。 k 最短路径问题通常包括两类:有限制的k 最短路问题和无限制的K 最短路问题。 前者要求最短路径集合不含有回路,而后者对所求得的...
  • 算法解决的是有向图单个源点到其他顶点的最短路径问题。举例来说,如果图的顶点表示城市,而边上的权重表示著城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 147
精华内容 58
关键字:

matlab中最短路径问题

matlab 订阅