图论模型-迪杰斯特拉算法和贝尔曼福特算法★★★★

该博客为个人学习清风建模的学习笔记,部分课程可以在B站:【强烈推荐】清风:数学建模算法、编程和写作培训的视频课程以及Matlab等软件教学_哔哩哔哩_bilibili

目录

​1图论基础

1.1概念

1.2在线绘图

1.2.1网站

1.2.2MATLAB

1.3无向图的权重邻接矩阵 

1.4有向图的权重邻接矩阵

2迪杰斯特拉算法

2.1概念

2.2步骤

2.3问题

3贝尔曼福特算法

3.1概念

3.2负权回路

3.3代码

3.3.1计算最短路径

3.3.2返回任意两点的距离矩阵

3.3.3找给定范围内所有的点 

3.3.4示例代码 

 4总结


名称重要性难度
图论最短路径求解:迪杰斯特拉算法和贝尔曼福特算法★★★★★★★

1图论基础

1.1概念

图论中的图( Graph )是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事
物间具有这种关系。
一个图可以用数学语言描述为 G(V(G),E(G)) V(vertex) 指的是图的顶点集,E(edge) 指的是图的边集。
根据边是否有方向,可将图分为有向图和无向图。
另外,有些图的边上还可能有权值,这样的图称为有权图。

1.2在线绘图

1.2.1网站

https://csacademy.com/app/graph_editor/

1.2.2MATLAB

注:( 1 Matlab 做出来的图不是很漂亮,要是节点比较少,还是推荐大家使用在线作图。 2 )该函数在 2015b 之后的版本才支持,如果运行出错请下载新版本 Matlab

代码全部摘自清风老师: 

%% 注意:以下代码需要较新版本的matlab才能运行(最好是2016版本及以上哦)
% 如果运行出错请下载新版的matlab代码再运行%% Matlab作无向图
% (1)无权重(每条边的权重默认为1)
% 函数graph(s,t):可在 s 和 t 中的对应节点之间创建边,并生成一个图
% s 和 t 都必须具有相同的元素数;这些节点必须都是从1开始的正整数,或都是字符串元胞数组。
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)
% 注意哦,编号最好是从1开始连续编号,不要自己随便定义编号
s1 = [1,2,3,5];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)% 注意字符串元胞数组是用大括号包起来的哦
s2 = {'学校','电影院','网吧','酒店'};
t2 = {'电影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2, 'linewidth', 2)  % 设置线的宽度
% 下面的命令是在画图后不显示坐标
set( gca, 'XTick', [], 'YTick', [] );  % (2)有权重
% 函数graph(s,t,w):可在 s 和 t 中的对应节点之间以w的权重创建边,并生成一个图
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  %% Matlab作有向图
% 无权图 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)
set( gca, 'XTick', [], 'YTick', [] );  % 有权图 digraph(s,t,w)
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) 
set( gca, 'XTick', [], 'YTick', [] );  

1.3无向图的权重邻接矩阵 

Inf指代权重为无穷

1.4有向图的权重邻接矩阵

2迪杰斯特拉算法

2.1概念

算法讲解视频地址:
https://www.bilibili.com/video/av54668527

2.2步骤

2.3问题

按照该算法,从1到2的最短路径为2,路径为1\rightarrow 2,但实际从1\rightarrow 3\rightarrow 2的距离为1,才是真正的最短路径。

3贝尔曼福特算法

3.1概念

为了解决迪杰斯特拉算法不能应用于负权重问题,引入贝尔曼福特算法。

该算法不支持含有负权回路的图。

 有兴趣的同学可以参考下面两份资料弄懂其实现原理:

https://blog.csdn.net/a8082649/article/details/81812000
https://www.bilibili.com/video/av43217121

3.2负权回路

含有负权重的无向图都是负权回路

3.3代码

3.3.1计算最短路径

Method可选参数
选项说明
'auto' 默认值)
'auto'  选项会自动选择算法:
'unweighted'  用于没有边权重的 graph  digraph  输入。
'positive'  用于具有边权重的所有 graph  输入,并要求权
重为非负数。此选项还用于具有非负边权重的 digraph 
入。
'mixed'  用于其边权重包含某些负值的 digraph  输入。图
不能包含负循环。
'unweighted'
广度优先计算,将所有边权重都视为 1
'positive' 
Dijkstra 算法,要求所有边权重均为非负数。
'mixed' 仅适用于 digraph即有向图
适用于有向图的 Bellman‐Ford  算法,要求图没有负循环。
尽管对于相同的问题, 'mixed'  的速度慢于 'positive' ,但
'mixed'  更为通用,因为它允许某些边权重为负数。

3.3.2返回任意两点的距离矩阵

3.3.3找给定范围内所有的点 

3.3.4示例代码 

代码全部摘自清风老师

%% 注意:以下代码需要较新版本的matlab才能运行(最好是2016版本及以上哦)
% 如果运行出错请下载新版的matlab代码再运行% 注意哦,Matlab中的图节点要从1开始编号,所以这里把0全部改为了9
% 编号最好是从1开始连续编号,不要自己随便定义编号
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) 
set( gca, 'XTick', [], 'YTick', [] );  
[P,d] = shortestpath(G, 9, 4)  %注意:该函数matlab2015b之后才有哦% 在图中高亮我们的最短路径
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);  %首先将图赋给一个变量
highlight(myplot, P, 'EdgeColor', 'r')   %对这个变量即我们刚刚绘制的图形进行高亮处理(给边加上r红色)% 求出任意两点的最短路径矩阵
D = distances(G)   %注意:该函数matlab2015b之后才有哦
D(1,2)  % 1 -> 2的最短路径
D(9,4)  % 9 -> 4的最短路径% 找出给定范围内的所有点  nearest(G,s,d)
% 返回图形 G 中与节点 s 的距离在 d 之内的所有节点
[nodeIDs,dist] = nearest(G, 2, 10)   %注意:该函数matlab2016a之后才有哦

 4总结

该章节主要是为了解决图论中最短路径问题的两种算法,迪杰斯特拉算法是基于贪心思想的一种算法,但是不能够解决含有负权值的问题,而贝尔曼福特算法可以解决迪杰斯特拉算法的不足,但是同样不能解决含有负权回路的最短路径问题。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【毕业论文】| 基于Unity3D引擎的冒险游戏的设计与实现

📢博客主页:肩匣与橘 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由肩匣与橘编写,首发于CSDN🙉 📢生活依旧是美好而又温柔的,你也…

学生成绩管理系统(C语言)

系统分析 1. 主菜单的实现 2. 增加人员功能的实现 3. 删除数据功能的实现 4. 编辑人员功能的实现 5. 排序功能的实现 6. 输出功能 7. 查找信息功能 具体代码 #include <stdio.h> #include <string.h> #include <stdlib.h> #define SIZE 100000typedef struc…

level 6 day2-3 网络基础2---TCP编程

1.socket&#xff08;三种套接字&#xff1a;认真看&#xff09; 套接字就是在这个应用空间和内核空间的一个接口&#xff0c;如下图 原始套接字可以从应用层直接访问到网络层&#xff0c;跳过了传输层&#xff0c;比如在ubtan里面直接ping 一个ip地址,他没有经过TCP或者UDP的数…

MVCC数据库并发控制技术

一、引言 MVCC&#xff08;Multi-Version Concurrency Control&#xff09;是一种广泛使用的数据库并发控制技术&#xff0c;它允许数据库读操作和写操作并发执行&#xff0c;而无需加锁整个表或行&#xff0c;从而大大提高了数据库的并发性能和吞吐量。MVCC主要被应用于支持事…

最新全新UI异次元荔枝V4.4自动发卡系统源码

简介&#xff1a; 最新全新UI异次元荔枝V4.4自动发卡系统源码 更新日志&#xff1a; 1增加主站货源系统 2支持分站自定义支付接口 3目前插件大部分免费 4UI页面全面更新 5分站可支持对接其他分站产品 6分站客服可自定义 7支持限定优惠 图片&#xff1a; 会员中心截图&…

docker默认存储地址 var/lib/docker 满了,换个存储地址操作流程

1. 查看docker 存储地址 docker info如下 var/lib/docker2、查看内存大小 按需执行 df -h 找超过100M的大文件 find / -type f -size 100M -exec ls -lh {} \; df -Th /var/lib/docker 查找这个文件的容量 df -h 查找所有挂载点 du -hs /home/syy_temp/*1、df -h 2、sud…

Java中锁的全面详解(深刻理解各种锁)

一.Monitor 1. Java对象头 以32位虚拟机位例 对于普通对象,其对象头的存储结构为 总长为64位,也就是8个字节, 存在两个部分 Kclass Word: 其实也就是表示我们这个对象属于什么类型,也就是哪个类的对象.而对于Mark Word.查看一下它的结构存储 64位虚拟机中 而对于数组对象,我…

卡片式组件封装demo

效果视频&#xff1a; 卡片组件 样式还得细调~&#xff0c;时间有限&#xff0c;主要记录一下逻辑。 html结构&#xff1a; 目录 父组件数据处理数据格式 父组件的全部代码 子组件数据处理props参数 样式部分三个圆点点击三圆点在对应位置显示查看弹框点击非内容部分隐藏查看…

从千台到十万台,浪潮信息InManage V7解锁智能运维密码

随着大模型技术的深度渗透&#xff0c;金融行业正经历着前所未有的智能化变革。从“投顾助手”精准导航投资蓝海&#xff0c;到“智能客服”秒速响应客户需求&#xff0c;大模型以其对海量金融数据的深度挖掘与高效利用&#xff0c;正显著提升金融服务的智能化水准&#xff0c;…

Python爬虫(2) --爬取网页页面

文章目录 爬虫URL发送请求UA伪装requests 获取想要的数据打开网页 总结完整代码 爬虫 Python 爬虫是一种自动化工具&#xff0c;用于从互联网上抓取网页数据并提取有用的信息。Python 因其简洁的语法和丰富的库支持&#xff08;如 requests、BeautifulSoup、Scrapy 等&#xf…

Springboot同时支持http和https访问

springboot默认是http的 一、支持https访问 需要生成证书&#xff0c;并配置到项目中。 1、证书 如果公司提供&#xff0c;则直接使用公司提供的证书&#xff1b; 如果公司没有提供&#xff0c;也可自己使用Java自带的命令keytool来生成&#xff1a; &#xff08;1&#x…

postman创建mock server

B站博主的说明&#xff1a;

开源模型应用落地-FastAPI-助力模型交互-进阶篇-RequestDataclasses(三)

一、前言 FastAPI 的高级用法可以为开发人员带来许多好处。它能帮助实现更复杂的路由逻辑和参数处理&#xff0c;使应用程序能够处理各种不同的请求场景&#xff0c;提高应用程序的灵活性和可扩展性。 在数据验证和转换方面&#xff0c;高级用法提供了更精细和准确的控制&#…

【05】LLaMA-Factory微调大模型——初尝微调模型

上文【04】LLaMA-Factory微调大模型——数据准备介绍了如何准备指令监督微调数据&#xff0c;为后续的微调模型提供高质量、格式规范的数据支撑。本文将正式进入模型微调阶段&#xff0c;构建法律垂直应用大模型。 一、硬件依赖 LLaMA-Factory框架对硬件和软件的依赖可见以下…

广州机房搬迁网络部署方案

新机房网络部署应包括核心模块、业务模块、光传输模块、安全模块、流量采集模块、路由模块、带外管理模块等&#xff0c;每个模块都根据业务需求规划成多个POD&#xff08;Point Of Delivery&#xff0c;基本物理设计单元&#xff09;。 核心模块部署主要实现各业务模块的高速互…

【D3.js in Action 3 精译_018】2.4 向选择集添加元素

当前内容所在位置 第一部分 D3.js 基础知识 第一章 D3.js 简介&#xff08;已完结&#xff09; 1.1 何为 D3.js&#xff1f;1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践&#xff08;上&#xff09;1.3 数据可视化最佳实践&#xff08;下&#xff09;1.4 本章小结 第二章…

Express+mysql单表分页条件查询

声明&#xff08;自己还没测试过&#xff0c;只提供大概逻辑&#xff0c;什么多表连接查询可以在原基础上添加&#xff09; class /*** param connection Express的mysql数据库链接对象* current 当前页* pageSize 一页显示行数* where [{key:id,operator:,value15}], key查询…

js拖拽div的例子

当需要在网页中实现拖拽功能时&#xff0c;可以使用JavaScript来实现。下面是一个简单的例子&#xff0c;演示如何实现拖拽一个 <div> 元素&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <…

动态路由协议 —— EIGRP 与 OSPF 的区别

EIGRP&#xff08;增强内部网关路由协议&#xff09;和 OSPF&#xff08;开放式最短路径优先&#xff09;是两种最常见的动态路由协议&#xff0c;主要是用来指定路由器或交换机之间如何通信。将其应用于不同的情况下&#xff0c;可提高速率、延迟等方面的性能。那么它们之间到…

微信小程序数组绑定使用案例(二)

一、数组事件绑定&#xff0c;事件传递数据 1.wxml <text>姓名&#xff1a;{{name}} </text> <block wx:for"{{list}}"><button bind:tap"nameClick2" data-name"{{item}}">修改:{{item}}</button> </block&…