数学建模--图论最短路径基础

1.图的定义

学过数据结构或者离散数学的小伙伴们应该知道图的概念,我在这里简单的介绍一下:

图的概念和我们理解的是很不一样的,这里的图并不是我们的生活里面的图片,而是一种表示不同的数据之间的关系,例如这里的5个节点,不同的节点之间的关系使用箭头进行表示,这里的1指向2的箭头表示12之间的一种关系;

图里面的不同的节点之间的距离表示的实际含义是根据这个题目的实际意义确定的,我们要看具体的题目,这里的节点之间的横线上面的数值表示的是一种权重;

2.图的种类

有方向的图和无方向的图,无方向的图也叫做双向的图,例如两个城市之间的道路;

3.图的数学语言

我们数学建模的时候使用的是矩阵进行运算的,这里的矩阵叫做邻接矩阵,这里的矩阵是一个方阵,矩阵的大小是根据结点的个数决定的;

这里的邻接矩阵里面的每个元素代表的意义是什么呢?图上有一个简单的分段函数,当不同的两个节点之间有关系的时候,例如我们的12之间有10这个权重,我们就在这个邻接矩阵的第一行第二列写上10就可以了;

0和无穷本质上是没有区别的,但是我们还是既使用0,也是用无穷,这里的0就代表的是自己和自己之间的关系,所以我们可以观察到这个矩阵的主对角线上面的元素都是0;

无穷表示的就是两个节点之间没有关系,例如4没有指向5的关系,所以4行5列的元素就是无穷,5有指向4的关系,所以5行4列的元素就是对应的权重2;

4.单源最短路径

上面的就是单源最短路径的一个具体的例子,下面的是简单的介绍:

(1)路径长度是一个专有的名词,并不是指两个地点之间的距离,而是根据实际的问题决定的;

(2)在这个例子里面的路径长度就是对应的路径的最小权重,在成本问题里面,这个路径长度就是对应的成本,我们的最短路径长度就是指的成本的最小值;

(3)最短路径的实质就是:最短路径的子路径其实也是最短路径,怎么进行理解呢?

对于上面的这张图片,我们可以看到的是12456这5个节点,假设我们已经知道了1到6的最短路径就是1256,那么这个最短路径的子路径125就是1到5的最短路径;

5.适用的赛题

(1)第一类肯定就是最短路径问题,从一个地方到另外的一个地方,要让这个距离最短,这个就是一个典型的最短路径问题;

(2)就是涉及到设备的更新问题,在一定的年限里面,我们如何进行分配是否购买新设备,旧的设备需要一定的维修费,新的设备需要购买的费用;时间越长,维修的成本就会越高,这个其实也是最短路径的范畴,我们后续会使用相关的题目进行介绍;

6.模型介绍

这里使用的是Dijkstra算法:

(1)我们首先圈定1这个节点,对照右边的这个表格,右边的这个表格是一列一列看的,每一列代表的是一次能完整的过程;

(2)圈定1这个节点之后,找1到其他的结点的路径,1->2是10,1->3和1->4都是没有直接的路径的,所以我们使用无穷进行表示;1->5的路径是存在的,所以表格里面的第一列的第五行写的是5;这样第一轮比较完成之后的最小路径就是1到2;

(3)然后我们圈定15这两个节点,看看这个圈里面的到其他的节点之间的距离,内部节点是可以走动的,例如15到节点2的距离,可以是12这个距离就是10,也可以是152,这个距离就是8,显然8更优,15到3这个节点只可以是153是14,如果是123的话之间要经过2这个节点,所以不行;15到4的话就是154距离就是7;第二轮比较完成之后154的距离是最小的;

(4)接下来我们圈定的是154,其中152是最短的,路径的长度是8,到3的话,1543的路径是最短的,距离是13;

(5)最后的一轮,我们圈定的是1245,最短的路径就是1523,最短距离是9;

这几轮的比较完成之后,我们就已经找到了不同的节点之间的最短的路径,就是我们的表格左边的那张图,这样我们的1节点到其他的节点之间的最短的距离就已经很明确了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/584152.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CMMI认证--基础知识总览

最近公司研发部搞CMMI L5认证,顺便记录下培训内容。 文章目录 一、什么是CMMI二、CMMI作用三、CMMI的成熟度等级四、过程域五、此次CMMI DEV 2.0或3.0特点六、CMMI 评估1、评估方法2、客观证据3、每个过程域如何给出评分等级 七、CMMI规程文件八、CMMI L5将度量统计…

Re69:读论文 LaMDA: Language Models for Dialog Applications

诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文名称:LaMDA: Language Models for Dialog Applications ArXiv网址:https://arxiv.org/abs/2201.08239 本文介绍谷歌提出的对话大模型LaMDA,主要关注对各项指标&#x…

【C 数据结构】深度优先搜索、广度优先搜索

文章目录 【 1. DFS 深度优先搜索 】1.1 基本原理1.2 C 实现 【 2. BFS 广度优先搜索 】2.1 基本原理2.2 C 实现 【 3. 深度优先生成树、广度优先生成树 】【 4. 深度优先生成森林、广度优先生成森林 】4.1 深度优先生成森林4.2 广度优先生成森林 对存储的图中的顶点进行遍历搜…

【信号与系统杂谈 - 1】为什么拉普拉斯变换有收敛域而傅里叶变换没有

这个问题是我在推导傅里叶变换的时移特性公式和拉普拉斯变换的延时特性公式时发现的(即拉氏变换总是需要考虑收敛域的原因) 援引知乎上的回答解释

12_Scala_package

文章目录 Scaal面向对象编程1.回顾Java2.package可以多次声明3.设置作用域,设置上下级4.包可以当作对象使用5.import6.Scala用_取代Java *7.导入多个包8.屏蔽类9.类起别名10.import的规则11.有些包无需导入 Scaal面向对象编程 Scala是一门完全面向对象语言&#xf…

C# winform 漂亮的日期时间控件

源代码下载: https://download.csdn.net/download/gaoxiang19820514/89242240 效果图 在 HZH-Controls控件 基础上修改的日期控件 因为HZH_Controls控件 中的日期控件太大了, 我的程序中需要多个日期时间的控件放不下,主题是绿色的&#…

Springboot+Vue项目-基于Java+MySQL的校园疫情防控系统(附源码+演示视频+LW)

大家好!我是程序猿老A,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:Java毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计 &…

力扣刷题Day2

题目链接: 24. 两两交换链表中的节点 - 力扣(LeetCode) 效果: 解题思路: 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 注意不可以只是单纯的改变节点内部的值,而…

Docker--compose概述与部署

目录 一、概述 1. Compose简介 1.1 docker compose常用命令 1.2 Compose配置常用字段 2. YAML简介 2.1 YAML支持的数据结构 2.2 YML文件编写注意事项 2.3 Docker Compose文件结构 3. Docker-Compose安装 ​编辑 4.docker Compose撰写nginx 镜像 1. 准备环境 ​编辑…

苹果和OpenAI再续前缘,iOS 18会是颠覆级的吗?|TodayAI

据彭博社最新报道,苹果公司已经与人工智能领域的先锋企业OpenAI重启了对话,双方目前正在讨论一项可能的合作,以将OpenAI的生成式人工智能技术整合到苹果即将推出的iOS 18操作系统中。这一举措表明,苹果正加速其在人工智能技术上的…

【EI会议|稳定检索】2024年传感技术与图像处理国际会议(ICSTIP 2024)

2024 International Conference on Sensing Technology and Image Processing 一、大会信息 会议名称:2024年传感技术与图像处理国际会议会议简称:ICSTIP 2024收录检索:提交Ei Compendex,CPCI,CNKI,Google Scholar等会议官网:htt…

final原理

文章目录 1. 设置 final 变量的原理2. 获取 final 变量的原理 1. 设置 final 变量的原理 理解了 volatile 原理,再对比 final 的实现就比较简单了 public class TestFinal {final int a 20; }字节码 0: aload_0 1: invokespecial #1 // Method java/lang/Object…

数组 Leetcode 704 二分查找/Leetcode 59 螺旋矩阵/Leetcode 203移除链表元素

数组 Leetcode 704 二分查找 Leetcode 704 学习记录自代码随想录 二分法模板记忆&#xff0c;数值分析中牛顿迭代法 class Solution { public:int search(vector<int>& nums, int target) {int left 0, right nums.size()-1;// 是否需要等于号&#xff0c;假设…

SpringCloud之OpenFeign

学习笔记&#xff1a; 官网地址&#xff1a;https://docs.spring.io/spring-cloud-openfeign/docs/current/reference/html/#spring-cloud-feign 源码&#xff1a;https://github.com/spring-cloud/spring-cloud-openfeign 1、概念总结 OpenFeign是一个声明式的Web服务客户端…

MySql-日期分组

一、分别统计各时间各类型数据条数 数据库的 request_time字段 数据类型&#xff1a;timestamp 默认值&#xff1a;CURRENT_TIMESTAMP 例子&#xff1a; 2024-01-26 08:25:48 原数据&#xff1a; 1、将数据按照日期&#xff08;年月日&#xff09;形式输出 按照request_…

【人工智能基础】聚类实验分析

实验环境&#xff1a;anaconda、jupyter notebook、spyder 实现用到的类库&#xff1a;numpy、matplotlib、scikit-learn k均值聚类&#xff08;K-MEANS&#xff09; k均值聚类的原理&#xff1a; 选定k个聚类中心把数据集中距离聚类中心i最近的点都归属到一个簇根据每个簇中…

debian配置四叶草输入法

效果展示 一、前言 在linux下体验比较好的输入法只有两款&#xff1a;搜狗输入法、四叶草输入法。 ubuntu下可以成功配置搜狗输入法&#xff0c;但debian下从来没有成功过。 今天在用fcitx5 四叶草时发现VNC远程输入法会失灵&#xff0c;于是改用了ibus 四叶草&#xff0c…

C# wpf 运行时替换方法实现mvvm自动触发刷新

文章目录 前言一、如何实现&#xff1f;1、反射获取属性2、定义替换方法3、交换属性的setter方法 二、完整代码1、接口2、项目 三、使用示例1、倒计时&#xff08;1&#xff09;、继承ViewModelBase&#xff08;2&#xff09;、定义属性&#xff08;3&#xff09;、属性赋值&am…

小程序地理位置接口怎么开通?

小程序地理位置接口有什么功能&#xff1f; 如果我们提审后驳回理由写了“当前提审小程序代码包中地理位置相关接口( chooseAddress、getLocation )暂未开通&#xff0c;建议完成接口开通后或移除接口相关内容后再进行后续版本提审”&#xff0c;如果你也碰到类似问题&#xf…

C#基础之冒泡排序

排序初探 文章目录 冒泡排序1、概念2、冒泡排序的基本原理3、代码实现思考1 随机数冒泡排序思考2 函数实现排序 冒泡排序 1、概念 将一组无序的记录序列调整为有序的记录序列&#xff08;升、降序&#xff09; 2、冒泡排序的基本原理 两两相邻&#xff0c;不停比较&#x…