当前位置: 首页 > news >正文

用MATLAB求最短路径(graphshortestpath)和求最小生成树(minspantree),代码演示

求最短路径(graphshortestpath),求最小生成树(minspantree)

文章目录

    • 求最短路径(graphshortestpath),求最小生成树(minspantree)
      • 1、最短路径问题
      • 2、最小生成树

1、最短路径问题

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

  • 图:边和节点组成的结构,在数学建模中例如本题中道路和城市。
  • 边:带有方向的是有向图,否则为无向图。
  • 权重:每条边都有与之对应的值,本题中边道路,边的权重就是道路长度,当然是越小越好。

MATLAB求解最短路径:**Dijkstra算法,或MATLAB的graphshortestpath**函数

例:image-20240105134622985

%sparse生成稀疏矩阵,也就是除了注明的几个元素外,其余都是0
%spare里第一个和第二个矩阵相同位置的元素值就是非零元素的索引
%非零元素的值
%w是每条边的权值
w=[10,5,2,1,4,6,7,3,9,2]
DG = sparse([1,1,2,2,3,4,4,5,5,5],[2,5,5,3,4,3,1,2,3,4],w)
% 没有就默认为零,这样快速生成一个稀疏矩阵

生成image-20240105134301179

% dist是最短路径的值, path是最短路径的节点顺序
% pred是到每一个节点的最短路径的终点前一个节点
% 如果求节点1到其他所有节点的最短路径呢?
[dist,path,pred] = graphshortestpath(DG,1,3)  %后面的数字参数是起点和终点,然后计算最短路径

显示

% biograph生成图对象; view显示该图
point_name =["城市1", "城市2", "城市3","城市4", "城市5"]
h = view(biograph(DG,point_name, 'Showweights', 'on'))

优化

% 将最短路径的节点和边缘标记为红色并增加线宽
% getedgesbynodeid得到图h的指定边的句柄
% 第一个参数是图,第二个是边的出点,第三个是边的入点%句柄确保能找到对应的东西
% get查询图的属性,h.Nodes(path), 'ID'得到图h中最短路径的
% set函数设置图形属性
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); %选取最短路径,并找到ID 
set(edges,'LineColor', [1 0 0])% RGB数值,红绿蓝
set(edges,'Linewidth',2)

最终结果:image-20240105135745136

2、最小生成树

  • 最短路径的区别:最短路径是针对某一顶点作为起点而言的,最小生成树是所有顶点连通总路径最小

  • 最小生成树的求解:

    MATLAB的minspantree函数求解最小生成树,还有克鲁斯卡尔(Kruskal)算法,和普利姆(Prim)算法。

image-20240105141235495

minspantree函数演示:

s = [1,1,2,2,3,3,4,4,4,5];
t = [2,3,4,5,4,7,5,6,7,6];
weights = [50,60,65,40,52,45,50,30,42,70];
%生成无向图,其中s和t对应元素代表着边,weights是权值
G= graph(s,t,weights);
%求出最小生成树,得到的T包含最小生成树的节点和对应边的权
T= minspantree(G);% p = plot(G)就能把图片展现出来,后面是为了美观设置字体等
p = plot(G, 'EdgeLabel ',G.Edges.weight,"MarkerSize",8,'NodeFontSize',16,'EdgeFontSize',16)%highlight突出显示绘制的图中的节点和边
highlight(p,T,'EdgeColor','red',"Linewidth",3)  

在上述的代码中,T里面存的就是最小的生成树,而后续的操作只是为了更加的美观。
运行结果:
image-20240105152003423

相关文章:

用MATLAB求最短路径(graphshortestpath)和求最小生成树(minspantree),代码演示

求最短路径(graphshortestpath),求最小生成树(minspantree) 文章目录 求最短路径(graphshortestpath),求最小生成树(minspantree)1、最短路径问题2、最小生成…...

用win系统搭建Minecraft世界服务器,MC开服教程,小白开服教程

雨云VPS用Windows系统搭建我的世界世界服务器,Minecraft开服教程,小白开服教程,MC 1.19.4版本服务器搭建教程。 此教程使用 Mohist 1.19.4 服务端,此服务端支持Forge模组和Bukkit/Spigot/Paper插件,如果需要开其他服务…...

MacOS安装Miniforge、Tensorflow、Jupyter Lab等(2024年最新)

大家好,我是邵奈一,一个不务正业的程序猿、正儿八经的斜杠青年。 1、世人称我为:被代码耽误的诗人、没天赋的书法家、五音不全的歌手、专业跑龙套演员、不合格的运动员… 2、这几年,我整理了很多IT技术相关的教程给大家&#xff0…...

iOS 应用上架指南:资料填写及提交审核

摘要 本文提供了iOS新站上架资料填写及提交审核的详细指南,包括创建应用、资料填写-综合、资料填写-IOS App和提交审核等步骤。通过本指南,您将了解到如何填写正确的资料,并顺利通过苹果公司的审核。 引言 在开发iOS应用后,将其…...

车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 车速预测 | Matlab基于RBF径向基神经网络的车速预测模型(多步预测,尾巴图) 程序设计 完整程序和数据获取方式:私信博主回复Matlab基于RBF径向基神经网络的车速预测模型…...

MySQL 5.7.35下载安装使用_忘记密码_远程授权

文章目录 MySQL 5.7.35下载安装使用_忘记密码_远程授权MySQL下载地址mysql安装点击安装,最好以管理员身份运行选择自定义安装选择64位勾选启动自定义产品执行点击同意点击下一步点击执行下一步配置数据库端口号设置登录密码,如果密码忘记,下面…...

openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题

文章目录 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时间运行的问题194.1 分析查询语句长时间运行的问题194.1.1 问题现象194.1.2 原因分析194.1.3 处理办法 openGauss学习笔记-194 openGauss 数据库运维-常见故障定位案例-分析查询语句长时…...

GoLang:gRPC协议的介绍以及详细教程,从Protocol开始

目录 ​编辑 引言 一、安装相关Go语言库和相关工具 1. 安装Go 2. 安装Protocol Buffers Compiler 2.1 Windows 2.1.1 下载 2.1.2 解压 2.1.3 环境变量 2. macOS 3. Linux 4. 验证安装 3. 安装gRPC-Go 4. 安装Protocol Buffers的Go插件 二、定义服务 三、生成Go…...

LeetCode-2645. 构造有效字符串的最少插入数

给你一个字符串 word ,你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次,返回使 word 有效需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到,则认为该字符串有效 。 示例 1: 输入:word “b” …...

ssm+vue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频: ssmvue的城投公司企业人事管理系统设计与实现(有报告)。Javaee项目,ssm vue前后端分离项目。 项目介绍: 采用M(model)V(view)C(controller&#x…...

nginx基础面试题以及配置文件解析和命令控制

目录 1、nginx是什么 2、nginx的特点 3、为什么中国大陆有:百度、京东、新浪、网易、腾讯、淘宝等这么多用户使用nginx 4、nginx 的内部技术架构 上一期我们配置安装了nginx接着讲一下nginx配置文件的解析和nginx 命令控制 感谢观看!希望能够帮助到…...

全自动网页生成系统网站源码重构版

源码优点: 所有模板经过精心审核与修改,完美兼容小屏手机大屏手机,以及各种平板端、电脑端和360浏览器、谷歌浏览器、火狐浏览器等等各大浏览器显示。 免费制作 为用户使用方便考虑,全自动网页制作系统无需繁琐的注册与登入,直…...

【算法每日一练]-动态规划 (保姆级教程 篇16) #纸带 #围栏木桩 #四柱河内塔

目录 今日知识点: 计算最长子序列的方案个数,类似最短路径个数问题 四柱河内塔问题:dp[i]min{ (p[i-k]f[k])dp[i-k] } 纸带 围栏木桩 四柱河内塔 纸带 思路: 我们先设置dp[i]表示从i到n的方案数。 那么减法操作中&#xff…...

Grounding 模型 + SAM 报错

引入 Grounding 目标检测模型串联 SAM 从而实现实例分割任务,目前支持 Grounding DINO 和 GLIP 参考教程 MMDetection-SAM 如果是 Grounding DINO 则安装如下依赖即可 cd playground pip install githttps://github.com/facebookresearch/segment-anything.git pip…...

linux 网络基础配置

将Linux主机接入到网络,需要配置网络相关设置一般包括如下内容: 主机名 iP/netmask (ip地址,网关) 路由:默认网关 网络连接状态 DNS服务器 (主DNS服务器 次DNS服务器 第三个DNS服务器) 一、…...

leetcode-相同的树

100. 相同的树 使用递归的方法 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution:def isSameTree(self, p: …...

Leetcode17-好数对的数目(1512)

1、题目 给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i < j &#xff0c;就可以认为这是一组 好数对 。 返回好数对的数目。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3,1,1,3] 输出&#xff1a;4 解释&#xff1a;有 4 组好数对&am…...

Ubuntu22.04开机左上角下划线闪烁不开机

按下CtrlAltF2&#xff0c;打开TTY系统&#xff0c;然后通过用户名和密码登录&#xff0c;随后使用 sudo apt --fix-broken install 根据提示排除错误信息&#xff0c;然后使用apt安装lightdm安装就行。 tips:当使用EasyConnect的时候&#xff0c;你可能参考了下面这篇文章知…...

提升测试多样性,揭秘Pytest插件pytest-randomly

大家可能知道在Pytest测试生态中&#xff0c;插件扮演着不可或缺的角色&#xff0c;为开发者提供了丰富的功能和工具。其中&#xff0c;pytest-randomly 插件以其能够引入随机性的特性而备受欢迎。本文将深入探讨 pytest-randomly 插件的应用&#xff0c;以及如何通过引入随机性…...

C++学习笔记(三十二):c++ 堆内存与栈内存比较

本节对堆和栈内存进行描述。 应用程序启动后&#xff0c;操作系统将整个程序加载到内存&#xff0c;分配相应的物理ram&#xff0c;确保程序可以正常运行。堆和栈是ram中存在的两个区域。栈通常是一个预定义大小的内存区域&#xff0c;一般是2M字节左右。堆也是预定了默认值的…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...