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

【学习笔记】Matlab和python双语言的学习(图论最短路径)

文章目录

  • 前言
  • 一、图论
    • 基本概念
    • 示例
  • 二、代码实现----Matlab
  • 三、代码实现----python
  • 总结


前言

通过模型算法,熟练对Matlab和python的应用。
学习视频链接:
https://www.bilibili.com/video/BV1EK41187QF?p=36&vd_source=67471d3a1b4f517b7a7964093e62f7e6

一、图论

图论(Graph Theory)是数学和计算机科学中的一个重要分支,专门研究图(graphs)的性质及其应用。图是一种抽象的数据结构,用于表示对象及其相互关系。

基本概念

  1. 图(Graph)
    一个图由一组顶点(或称为节点)和一组边(连接这些顶点的线)组成。形式上,一个图 ( G ) 可以表示为 ( G = (V, E) ),其中 ( V ) 是顶点集合,( E ) 是边集合。

  2. 顶点(Vertex)
    图中的一个基本单位,代表某个对象。顶点的集合通常用 ( V ) 表示。

  3. 边(Edge)
    顶点之间的连接。边的集合通常用 ( E ) 表示。边可以是有向的(directed)或无向的(undirected)。

  4. 有向图(Directed Graph or Digraph)
    边有方向的图,即边表示从一个顶点指向另一个顶点的箭头。

  5. 无向图(Undirected Graph)
    边没有方向的图,即边仅表示顶点之间的连接,没有方向性。

  6. 权重(Weight)
    在一些图中,边可以附带一个数值,称为权重(weight),表示顶点之间的距离、成本或其他度量。

  7. 路径(Path)
    从一个顶点到另一个顶点经过的一系列边和顶点。路径的长度通常表示为路径上所有边的权重之和。

示例

在这里插入图片描述

  • 求 0 到 8 的最短距离。

二、代码实现----Matlab

在MATLAB中,shortestpath 函数用于计算图中两个节点之间的最短路径。

shortestpath 函数的基本语法如下:

[P, d] = shortestpath(G, s, t)
  • G:一个图对象,通常使用 graphdigraph 函数创建。
  • s:起始节点。
  • t:目标节点。
  • P:返回的最短路径上的节点序列。
  • d:返回的最短路径的长度(或权重和)。
% 定义图的边和权重
s = [9 9 1 1 3 3 3 2 2 5 5 7 7 8]; % 起始节点编号
t = [1 2 2 3 4 6 7 4 5 4 7 6 8 6]; % 终止节点编号
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9]; % 边的权重% 创建一个图形对象 G
G = graph(s,t,w);% 绘制图形 G,并将边的权重添加到图形上
% G.Edges.Weight 表示图形对象 G 中所有边的权重值,'EdgeLabel' 表示在图形上显示这些权重值
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
% 隐藏图形的坐标轴
set( gca, 'XTick', [], 'YTick', [] );% shortestpath 函数计算从节点 9 到节点 8 的最短路径和路径长度,并将路径和路径长度分别存储在 P 和 d 中
[P,d] = shortestpath(G, 9, 8);
% 在图形 G 中高亮显示最短路径
% highlight 函数高亮图形对象 myplot 中的路径 P,'EdgeColor', 'r' 表示将路径颜色设置为红色。
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);
highlight(myplot, P, 'EdgeColor', 'r')

运行结果:
在这里插入图片描述

三、代码实现----python

在 Python 中,可以使用 NetworkX 库和 Matplotlib 库来实现带有权重的无向图的创建和绘制。

import networkx as nx
import matplotlib.pyplot as plt# 定义图的边和权重
edges = [(9, 1, 4), (9, 2, 8), (1, 2, 3), (1, 3, 8), (3, 4, 2), (3, 6, 7), (3, 7, 4), (2, 4, 1), (2, 5, 6), (5, 4, 6), (5, 7, 2), (7, 6, 14), (7, 8, 10), (8, 6, 9)]# 创建一个有加权边的图形对象 G
G = nx.Graph()  
G.add_weighted_edges_from(edges)# 计算从节点 9 到节点 8 的最短路径和路径长度
path = nx.shortest_path(G, source=9, target=8, weight='weight')
path_length = nx.shortest_path_length(G, source=9, target=8, weight='weight')# 绘制图形 G,并将边的权重添加到图形上
pos = nx.spring_layout(G)  # 计算节点位置
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=10, width=2)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)# 在图形 G 中高亮显示最短路径
path_edges = list(zip(path, path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)# 隐藏图形的坐标轴
plt.gca().set_xticks([])
plt.gca().set_yticks([])# 显示结果
print('最短路径:', path)
print('最短路径长度:', path_length)plt.show()

运行结果:
在这里插入图片描述
在这里插入图片描述

总结

本文介绍了使用图论求最短路径,并通过典型示例建立模型,分别使用Matlab和python进行代码编写。

相关文章:

【学习笔记】Matlab和python双语言的学习(图论最短路径)

文章目录 前言一、图论基本概念示例 二、代码实现----Matlab三、代码实现----python总结 前言 通过模型算法,熟练对Matlab和python的应用。 学习视频链接: https://www.bilibili.com/video/BV1EK41187QF?p36&vd_source67471d3a1b4f517b7a7964093e6…...

vue.config.js 配置 devserve 配置

在 Vue CLI 项目中,devServer 配置用于设置开发服务器的行为。这包括了开发服务器的端口、主机名、是否开启 HTTPS、自动打开浏览器等设置,以及配置代理规则来解决跨域问题。 devServer 配置详解(version > 4.0.0) host: 设置开发服务器的主机地址&a…...

不入耳耳机什么牌子性价比高?五大年度必选款揭秘

和传统的入耳式耳机相比,开放式耳机采用的是不深入耳道的设计,佩戴舒适度更高,卫生健康,安全性也更高。同时音质表现也更加有空间感。想要体验开放式耳机带来的便利,就需要做好选购攻略,不入耳耳机什么牌子…...

SQL Zoo 6.The JOIN operation

以下数据均来自SQL Zoo 1.Modify it to show the matchid and player name for all goals scored by Germany. To identify German players, check for: teamid GER.(它以显示德国所有进球的比赛和球员名字,识别德国球员) SELECT matchid,player FROM goal where teamid GE…...

视频教程:Vue3移动端抽屉弹层组件实战

本教程演示了vue3的composition api实现的移动端h5抽屉弹层组件,录屏讲解包含了功能演示和具体的源码实现。 笔者相关教程: 使用tailwindcss轻松实现移动端rem适配Vue3.4双向绑定新特性:defineModel好用爱用 学习要点: 自定义…...

CSS 的 BFC(块级格式化上下文)

BFC是Block Formatting Context(块级格式化上下文)的缩写,是CSS中一个概念,用于描述页面上如何对元素进行布局。 BFC是一个独立的容器,它内部的元素不会受到外部容器的影响,同时它也会影响其内部元素的表现…...

【2023年】云计算金砖牛刀小试2

A场次题目:Openstack 平台部署与运维 control172.17.31.10compute172.17.31.20 compute任务1 私有云平台环境初始化 1.初始化操作系统 使用提供的用户名密码,登录竞赛云平台。根据表 1 中的 IP 地址规划,设置各服务器节点的 IP 地址,确保网络正常通信,设置控制节点主机名…...

python--将mysql建表语句转换成hive建表语句

1.代码 import json import sys import pymysqldef queryDataBase(tablename):# 连接数据库并查询列信息conn pymysql.connect(userroot, password123456, hosthadoop11)cursor conn.cursor()cursor.execute("SELECT column_name, data_type FROM information_schema.C…...

异步调用实践:Async,Future, TaskExecutor、EventListener

1. 异步调用概述 异步调用允许一个方法调用在不被当前线程阻塞的情况下继续执行,而调用者可以继续执行其他任务,直到异步操作完成。 在Spring Boot中,异步调用常用于提高应用的响应性和吞吐量,尤其是在处理长时间运行的任务时&a…...

Flask 异常处理

Flask 异常处理 使用 app.errorhandler 装饰器使用 app.handle_exception 装饰器使用 register_error_handler调试模式总结 在 Flask 应用中,异常处理是一个非常重要的部分,它可以帮助你管理运行时错误,提供友好的错误页面,以及记…...

【海思SS626 | 内存管理】海思芯片的OS内存、MMZ内存设置

😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...

linux crontab没有按照规则执行排查

配置了cron规则,但是一段时间后任务没有按预期执行,记录一次修复过程 检查crond服务 systemctl status crond规则正常 crontab -l脚本有执行权限 查看日志 第一种:journalctl journalctl -u crond | grep 03:00 -C 3-u 指定crond.serv…...

Cloudflare的D1使用技巧

总文档&#xff1a;https://developers.cloudflare.com/workers/wrangler/commands/#d1查询某个数据库中哪些命令占用资源最大&#xff1a; To find top 10 queries by execution count: npx wrangler d1 insights <database_name> --sort-typesum --sort-bycount --co…...

解决端口号被占用问题

第一种&#xff1a; 最简单有效的方法&#xff0c;重启一下电脑&#xff0c;占用此端口的程序就会释放端口。 第二种&#xff1a; 使用命令找到占用端口的程序&#xff0c;把它关闭。 1、打开运行窗口输入&#xff1a;CMD &#xff0c;进入命令窗口。 2、输入&#xff1a;n…...

如何在linux上部署zabbix监控工具

<1>搭建服务机 1&#xff09;首先我们先执行 sed -i s/SELINUXenforcing/SELINUXdisabled/ /etc/selinux/config ​ #然后我们再把防火墙开机自启关掉 马上生效 systemctl disable --now firewalld 2&#xff09;我们获得rpm包 rpm -Uvh https://mirrors.aliyun.com/…...

vulnhub系列:sp eric

vulnhub系列&#xff1a;sp eric 靶机下载 一、信息收集 nmap扫描存活&#xff0c;根据mac地址寻找IP nmap 192.168.23.0/24nmap扫描端口&#xff0c;开放端口&#xff1a;22、80 nmap 192.168.23.189 -p- -A -sV -Pndirb 扫描目录&#xff0c;.git 源码&#xff0c;admin…...

JVM二:JVM类加载机制

目录 前言 1.什么是类加载? 2.类加载整体流程 3.一个类什么时候被加载? 4.双亲委派模型 4.1 JVM默认提供了三个类加载器 4.1.1 BootstrapClassLoader 4.1.2 ExtensionClassLoader 4.1.3 ApplicationClassLoader 4.2 破坏双亲委派模型 前言 在上一篇文章中&#xf…...

对于springboot无法连接redis解决方案

对于springboot无法连接redis解决方案 一、测试是否能在本地应用上访问到你的redis&#xff08;如果是部署在linux上的话&#xff09;1. 开启telnet功能2. 开始测试端口是否能访问到&#xff08;适用于所有&#xff0c;包括MQ&#xff09;3. 开放6379端口4. 看spring的配置文件…...

关于android中的各种尺寸与计算

--张学友《心如刀割》很好听 先说几个术语&#xff1a; Screen size(屏幕尺寸)&#xff1a; 指的是手机实际的物理尺寸&#xff0c;比如常用的2.8英寸&#xff0c;3.2英寸&#xff0c;3.5英寸&#xff0c;3.7英寸 摩托罗拉milestone手机是3.7英寸 Aspect Ratio(宽高比率)&am…...

MySQL避免索引失效的方法详细介绍

避免索引失效 在MySQL中&#xff0c;索引是帮助MySQL高效获取数据的数据结构。它就像一本书的目录&#xff0c;通过索引可以快速定位到数据的具体位置&#xff0c;从而减少对数据库的扫描量&#xff0c;提高查询速度。索引可以存储在表中的一个或多个列上&#xff0c;创建索引…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...