精华内容
下载资源
问答
  • 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文件夹中提供了各种格式的测试数据。

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

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

    展开全文
  • 利用graphshortestpath 可以求最短路径,具体用法参考MATLAB帮助S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]; %边...

    利用graphshortestpath 可以求最短路径,具体用法参考MATLAB帮助

    S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量

    E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量

    W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]; %边权值向量,有向图,G(9,9)=0; 9个节点

    G=sparse(S,E,W); %关联矩阵的稀疏矩阵表示

    G(9,9)=0;

    P=biograph(G,[],'ShowWeights','on');%建立有向图对象P

    H=view(P);%显示各个路径权值

    [Dist,Path]=graphshortestpath(G,1,9,'Method','Dijkstra') %求节点1到节点9的最短路径

    set(H.Nodes(Path),'Color',[1 0.4 0.4]);%以下三条语句用红色修饰最短路径

    edges=getedgesbynodeid(H,get(H.Nodes(Path),'ID'));

    set(edges,'LineColor',[1 0 0]);

    set(edges,'LineWidth',2.0);

    以下是运行结果,节点1到节点9的最短路径为19

    Dist =

    19

    Path =

    1 3 4 5 7 9

    利用graphallshortestpaths可以求出所有最短路径

    Dists=graphallshortestpaths(G) %求所有最短路径

    Dists =

    0 1 2 5 9 6 16 12 19

    Inf 0 Inf 6 10 8 17 13 20

    Inf Inf 0 3 7 4 14 10 17

    Inf Inf Inf 0 4 2 11 7 14

    Inf Inf Inf Inf 0 Inf 7 Inf 10

    Inf Inf Inf Inf Inf 0 Inf 7 15

    Inf Inf Inf Inf Inf Inf 0 Inf 3

    Inf Inf Inf Inf Inf Inf Inf 0 10

    Inf Inf Inf Inf Inf Inf Inf Inf 0

    注意一点的是创建稀疏矩阵的时候,如果原始是m*3的矩阵a,分别表示起点、终点和权值,有n个点,用sparse(a),创建的还是m*3,这样根本不对,因为矩阵值是第三列,这样的话矩阵值包括了下标。应该是sparse(a(:,1),a(:,2),a(:,3)),这样的话是max(第一列)*max(第二列)的矩阵,然后设置spraseGraph(n,n)=0,这样的话sparseGraph才是方阵,采用调用系统的最短路径函数。

    clc

    clear all

    a = [6 1 1

    6 4 1

    6 5 1

    1 2 1

    2 3 1

    2 4 1

    3 5 1

    4 5 1];

    res = [];

    graph = sparse(a(:,1),a(:,2),a(:,3));

    graph(6,6) = 0;

    P=biograph(graph,[],'ShowWeights','on');%建立有向图对象P

    H=view(P);%显示各个路径权值

    718c1cc68f9f48e37a5b30b710c41877.png

    0cedfb2b3efa5fbe87cd66b2a09e7c50.png

    展开全文
  • MATLAB实现最短路径

    2021-08-30 22:55:17
    目录 一、Dijkstra是什么?...最短路径即从图的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as p

    目录

    一、Dijkstra是什么?

    二、算法介绍

    1.核心思想

    2.具体思路

    3MATLAB实现

    总结


    前言

    本人是数学建模在学习的小白,分享一下最近学习的内容也顺便做一下笔记。


    提示:以下是本篇文章正文内容,下面案例可供参考

    一、Dijkstra是什么?

    Dijkstra是解决最短路径的一种算法

    最短路径即从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径

    二、算法介绍

    1.核心思想

    广度优先搜索

    2.具体思路

    1.初始化,即所有的节点都是未访问节点(0),所有的距离都是无穷大(INF),所有的父亲节点都是-1,表示不存在。

    2.假设起点(A),然后对应的访问状态变为1,对应的距离变为0,其父亲节点变为本身。

    3.开始访问与起点相邻的节点(B)的信息(此时这些节点还没有被访问)

    更新规则如下:

    如果(A与B的距离加上A列表中的距离)小于(B列表中的距离),那么我们就将B列表中的距离更新为较小的距离,并将其父亲节点更新为A。

    4在所有未访问的节点里找到表格里具有最小距离的那个节点,并将其作为新的已访问节点。

    3MATLAB实现

    s = [9 9 1 1 2 2 2 7 7 6 6 5 5 4];
    t = [1 7 7 2 8 3 5 8 6 8 5 3 4 3 ];
    w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];%权重
    G = graph(s,t,w);
    plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);
    [P,D] = shortestpath(G,9,4);
    %%高亮显示路径
    myplot = plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);
    highlight(myplot,P,'EdgeColor','r');

    结果:


    三、总结

    这既是今天学习的内容。

    ——更新于2021.8.31

    展开全文
  • 本文将说明最短路径问题中的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-傻子也能看懂的弗洛伊德算法

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

    展开全文
  • 每一次迭代产生一个永久标号,把它接入到以起始点为v0根的树,在这棵树上每一个顶点与根结点之间的路径皆为最短路径。 1.3实例 寻找从顶点1到顶点5的最短路径: 一共有六个顶点,生成的带权邻接矩阵为:
  • 遗传算法解决最短路径问题matlab程序,并加以注释。 遗传算法解决最短路径问题matlab程序,并加以注释。
  • Dijkstra最短路径算法的Matlab实现 包括最短路径的打印子程序
  • matlab最短路径

    千次阅读 2020-11-14 21:35:14
    图论最短路径 (1)matlab作图 G = graph(s, t) 其中,s 和 t 都是节点组成的向量,表示从s 、t对应节点之间有边。 然后,plot(G)即可画出图。 G = graph(s, t, w) ...(2)Matlab计算最短路径 [P,d] = s
  • matlab求解最短路径

    万次阅读 多人点赞 2017-08-16 16:13:57
    matlab工具箱求图的最短路径
  • matlab 最短路径算法

    2015-06-09 09:46:29
    求两点家 最短路径,已经最短路径经过的其他节点情况
  • 最短路径问题(急)

    2021-04-25 00:07:15
    函数如下,如果需要源文件的话可以给我发邮件caoxd04@mails.tsinghua.edu.cnclearclc%% 构建距离矩阵% 在你的问题中直接使用题目内容构建距离矩阵% 没有连接的城市之间的距离可以用一个非常大的数表示n=12;...
  • 打开all.m将其中的语句复制下来,贴在命令窗口,可得到任意两点之间的最短路径,放在Muti_Cost矩阵直接运行all却会提示出错,真是搞不懂是什么原因,虽然这样可是功能已经比较强大了,只是稍微有一点麻烦。
  • MATLAB求解TSP最短路径问题 文章目录MATLAB求解TSP最短路径问题问题背景问题重述实现步骤Matlab 代码结果展示 问题背景 随着社会的不断进步,最短路径算法在人们的日常生活显得越来越重要。每天开车去上班,应该选择...
  • 基于MATLAB求解最短路问题,dijkstra最短路径算法的详细解读。
  • 该程序是matlab编写的,已知起点和终端,找到在指定的步数下,能到达的最短路径
  • 通过学习ACO算法来解释城市最短路径问题的算法。
  • matlab网络最短路径

    2021-04-18 12:04:08
    2.3 用 matlab 程序实现上述算法编写程序...C OLUMNS 特别企划 基于遗传算法的最短路径问题及其 MATLAB实现文/张书源 郭聪 前言在现实生活,我们经常遇到最 短路问题,例如寻找两点之间总长度最 短或者费用最低的...
  • 关于动态规划最短路径求解的matlab学习例子
  • Matlab编程求最短路径

    2021-10-12 16:23:11
    %以下构造一个图并求最短路径,注意图节点的编号从1开始,不能为0 clear %起点集 s = [9 9 9 9 9 9 9 9 1 1 1 2 2 2 3 4 5 5 6 7]; %终点集 e = [1 2 3 4 5 6 7 8 2 4 8 3 4 8 8 8 6 8 8 8]; %顶点到顶点的边上的...
  • 最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
  • 二、有向图最短路径 2.1基本知识 1.sparse是创建稀疏矩阵的一个函数,比如有一个3×3的一个矩阵,第一行值为1,2,3;第二行值为4,5,6;第三行值为7,8,9。(无向图) clear B=sparse([1 1 1 2 2 3],[1 2 3 1 ...
  • 利用matlab程序求复杂网络的最短路径,方法简便值得使用
  • MATLAB-K最短路径算法(KSP,K-shortest pathes)

    千次阅读 热门讨论 2020-10-16 17:30:12
    1959 年,霍夫曼(Hoffman) 和帕夫雷(Pavley)在论文第一次提出k 最短路径问题。 k 最短路径问题通常包括两类:有限制的k 最短路问题和无限制的K 最短路问题。 前者要求最短路径集合不含有回路,而后者对所求得的...
  • 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)(每次加入一个点然后更新最短路径矩阵D),D(n)是图的最短距离矩阵,同时引入一个后继点矩阵path记录两点间的最短路径。...
  • 1,6) %找顶点1到6的最短路径 % Mark the nodes and edges of the shortest path set(h.Nodes(path),'Color',[1 0.4 0.4]) %上色 edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 ...
  • 关于遗传算法的一个简单例子,在MATLAB中实现搜寻最短路径(最优化)的目的,仅供大家参考学习,谢谢
  • 利用Matlab编写的求解最短路径的Dijkstra算法,测试通过

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,511
精华内容 1,804
关键字:

matlab中最短路径问题

matlab 订阅