图论最短路径以及floyd算法的MATLAB实现

图论是数学的一个分支,起源于18世纪。1736年,数学家欧拉通过解决“哥尼斯堡七桥问题”,将问题抽象成点和线的关系,并通过理论分析得出结论,这个过程标志着图论的产生,欧拉也因此被称为“图论之父”。图论研究的是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,其中点代表事物,连接两点的线表示相应两个事物间具有这种关系。

一、无向图和有向图在图论中都是重要的概念,它们之间存在显著的区别。

首先,从定义上来看,无向图是一种由节点和边组成的数据结构,边没有方向性,也就是说,如果存在一条边(u, v),那么从u到v和从v到u都是可以的。这种图通常用来表示双向关系,如社交网络中的友谊关系。而有向图则是一种具有方向性的图,由一组顶点和一组有方向的边组成,每条方向的边都连着一对有序的顶点。在有向图中,如果存在一条边(u, v),那么只能从u到v,但不一定能从v到u。

此外,从应用角度来看,无向图主要用于表示双向关系,如社交网络、传输网络等,以及用于搜索最短路径等问题。而有向图则更多地用于表示具有方向性的关系,如流程、路径规划等。

二、在图论中,最短路径问题是一个经典问题,它涉及从图中某一顶点(源点)出发,到达另一顶点(终点)的所有路径中,寻找各边权值之和最小的路径,这种路径称为最短路径。

最短路径问题可以分为两类:单源最短路径问题和多源最短路径问题。单源最短路径问题是求单个顶点和其他所有顶点的最短路径,而多源最短路径问题则是求所有顶点相互之间的最短路径。对于最短路径问题,有多种算法可以用来求解,包括但不限于:

  1. Dijkstra算法:这是最短路径算法中最常用的一种。它基于贪心策略,通过逐步扩展路径来求解最短路径。算法的基本思想是,从一个起始顶点开始,逐步扩展到其他顶点,每次选择当前路径中距离起始顶点最近的顶点进行扩展,直到扩展到目标顶点或者所有顶点都被扩展完毕。
  2. Bellman-Ford算法:这也是另一种常用的最短路径算法。
  3. Floyd-Warshall算法:这是一种多源最短路径算法,可以求解图中任意两个顶点之间的最短路径。

以下面问题为例解决问题:

 

clear;clc;
% 注意Matlab中的图节点要从1开始编号
s = {'v1','v1','v1','v2','v3','v3','v4','v5','v5','v5','v5','v6','v6','v7','v9','v9'}; 
t = {'v2','v3','v4','v5','v2','v4','v6','v4','v6','v7','v8','v5','v7','v8','v5','v8'}; 
weight = [6,3,1,1,2,2,10,6,4,3,6,10,2,4,2,3];
%要做出有向图,只需要将graph改为digraph就行了 
G= digraph(s,t,weight);%有向图
myplot = plot(G,'EdgeLabel',G.Edges.Weight,'LineWidth',2);%图赋给一个变量 
set(gca,'XTick',[],'YTick',[]);
%[p,d] = shortestpath(G,start,end,[‘Method’,algorithm])
% 功能:返回图G中start节点到end节点的最短路径%输入参数:
% (1)G- 输入图 (graph 对象|digraph 对象)
% (2) start 起始的节点% 
% (3) end 目标的节点
% (4)[‘Method’,algorithm]是可选的参数,表示计算最短路径的算法。一般我% 们不用手动设置,默认使用的是“auto”,具体可设置的参数见下一页课件。% 输出参数:
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
% (1)P - 最短路径经过的节点 
% (2)d - 最短距离
[P,d] = shortestpath(G,'v1','v8')%求v1到v8的最短路径和距离

%在图中高亮出最短路径
highlight(myplot,P,'EdgeColor','red')

%任意两点的最短路径矩阵
D = distances(G)
D(1,8)%v1到v8的最短路径

下面是代码floyd算法的MATLAB实现:

gg = [0,inf,-2,inf;
      inf,0,inf,-1; 
      inf,2,0,inf;
      4,inf,3,0;];
[dist,path] = my_floyd(gg)
function [dist,path] = my_floyd(D)
[r,~]= size(D);
dist = D;
% 下面我们来初始化path矩阵
path = zeros(r);
for j= 1:r
    path(:,j) = j; %将第j列的元素变为j
end
for i = 1:r
    path(i,i) = -1;%将主对角线元素变为-1
end
for k=1:r%以k为中转
    for i=1:r %邻接矩阵第i行
        for j=1:r%邻接矩阵第j列
            if dist(i,j)>dist(i,k)+dist(k,j)
                dist(i,j)=dist(i,k)+dist(k,j);
                path(i,j)=path(i,k);
                % 起点为i,终点为j的两个节点之间的最短路径要经过的节点更新为path(i,k)
                % 注意,上面一行语句不能写成path(i,j) = k;
            end
        end
    end
end
end

 总的来说,图论是一门研究图与网络的理论学科,它在各个领域都发挥着重要的作用,为解决实际问题提供了有力的工具和方法。 

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

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

相关文章

机器人机械手加装SycoTec 4060 ER-S电主轴高精密铣削加工

随着科技的不断发展,机器人技术正逐渐渗透到各个领域,展现出前所未有的潜力和应用价值。作为机器人技术的核心组成部分之一,机器人机械手以其高精度、高效率和高稳定性的优势,在机械加工、装配、检测等领域中发挥着举足轻重的作用…

利用RWKV-Runner初步感受一下ai的世界

最近又听到群里的高手在讨论RWKV-Runner,于是没忍住,就想试试,没想到第一关就卡住了。 从群里大咖上传的RWKV-Runner_windows_x64.exe文件开始吧,又找了个虚拟机,直接放在桌面上运行一下,结果就跳出一堆文…

Java框架安全篇--Shiro-550漏洞

Java框架安全篇--Shiro-550漏洞 Shiro反序列化源码可以提取: https://codeload.github.com/apache/shiro/zip/shiro-root-1.2.4 JAVA反序列化就不说了,可以参考前面文章 https://blog.csdn.net/m0_63138919/article/details/136751184 初始Apache Sh…

安科瑞智慧安全用电综合解决方案

概述 智慧用电管理云平台是智慧城市建设的延伸成果,将电力物联网技术与云平台的大数据分析功能相结合,实现用电信息的可视化管理,可帮助用户实现安全用电,节约用电,可靠用电。平台支持web,app,微…

智慧交通(代码实现案例)

1.项目简介 目标: 了解智慧交通项目的架构知道智慧交通项目中的模块能够完成智慧交通项目的环境搭建 该项目是智慧交通项目,通过该项目掌握计算机视觉的方法在交通领域的相关应用,包括车道线检测的方法,多目标车辆追踪及流量统计方法&#…

1.4.1 着色器

着色器(Shader)是运行在GPU上的小程序,这些小程序为图形渲染管线的某个特定部分而运行,从基本意义上来说,着色器只是一种把输入转化为输出的程序。 一、着色器类QOpenGLShaderProgram QOpenGLShaderProgram是Qt中对着…

thinkadmin 新版安装步骤

1.通过 Composer 安装: ( 推荐方式,默认只安装 admin 模块 ) ### 创建项目( 需要在英文目录下面执行 ) composer create-project zoujingli/thinkadmin### 进入项目根目录 cd thinkadmin### 数据库初始化并安装 ### 默认使用 Sqlite 数据库,若使用其他数据库请按第二步修…

I.MX6ULL_Linux_驱动篇(57)linux Regmap API驱动

我们在前面学习 I2C 和 SPI 驱动的时候,针对 I2C 和 SPI 设备寄存器的操作都是通过相关的 API 函数进行操作的。这样 Linux 内核中就会充斥着大量的重复、冗余代码,但是这些本质上都是对寄存器的操作,所以为了方便内核开发人员统一访问 I2C/S…

当当狸智能激光雕刻机 多种材质自由雕刻,轻松打造独一无二的作品

提及“激光雕刻”,大多数人的印象一般都是:笨重巨大、价格昂贵、操作复杂、使用门槛较高、调试难度大...不是普通人能够随意操作的,让人望尘莫及。 而小米有品上新的这台「当当狸桌面智能激光雕刻机L1」,将超乎你的想象&#xff…

ABAP - 上传文件模板到SMW0,并从SMW0上下载模板

upload file template to SMW0 and download the template from it 首先上传文件到tcode SMW0 选择新建后,输入文件名和描述,再选择想要上传的文件 上传完成后: 在表WWWPARAMS, WWWDATA里就会有信息存进去 然后就可以程序里写代码了: 屏幕上的效果:

界面控件DevExpress WinForms/WPF v23.2 - 电子表格支持表单控件

DevExpress WinForm拥有180组件和UI库,能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForm能完美构建流畅、美观且易于使用的应用程序,无论是Office风格的界面,还是分析处理大批量的业务数据,它都能轻松胜任…

yolov9报错:AttributeError: ‘list‘ object has no attribute ‘view‘的两种解决方法

1. 报错问题 In loss_tal.py: pred_distri, pred_scores torch.cat([xi.view(feats[0].shape[0], self.no, -1) for xi in feats], 2).split( (self.reg_max * 4, self.nc), 1) The error is as follows: AttributeError: list object has no attribute vie…

5.递归分治——1.递归与函数调用

程序运行 指令 指令的划分以函数为单位,调用函数本质上是使用call指令将pc指针移动到被调用的函数函数调用完成,需要使用return返回,本质是pc移回调用函数位置 数据 函数调用时,在堆栈区域要申请一片栈帧,函数的局…

linux用户管理命令2

useradd可以创建用户,其执行具体表现为在home文件夹下创建对应文件 那么有了useradd添加用户,自然有passwd添加用户密码 userdel可以删除用户,其中-r命令删除用户及其文件,-f命令可以强制删除用户,即使用户当前正在登录…

LeetCode 面试经典150题 205.同构字符串

题目: 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字…

【MATLAB源码-第16期】基于matlab的MSK定是同步仿真,采用gardner算法和锁相环。

操作环境: MATLAB 2022a 1、算法描述 **锁相环(PLL)** 是一种控制系统,用于将一个参考信号的相位与一个输入信号的相位同步。它在许多领域中都有应用,如通信、无线电、音频、视频和计算机系统。锁相环通常由以下几个…

什么是公网IP?

公网IP,即公开网络IP地址,是指在互联网中公开可见、可访问的IP地址。每个设备在连接互联网时,都需要一个唯一的公网IP地址,以便其他设备可以定位并与之通信。 尽管公网IP在网络通信中具有重要作用,但它也带来了一些安全…

机器学习之聚类算法、随机森林

文章目录 随机森林决策树基础特征值问题? 聚类算法 随机森林 决策树 基础 概念:从根节点一步步走到叶子节点(决策); 组成:根节点第一个选择的节点;叶子节点最终的决策结果;非叶子…

汽车电子行业知识:智能汽车电子架构

文章目录 3.智能汽车电子架构3.1.汽车电子概念及发展3.2.汽车电子架构类型3.2.1.博世汽车电子架构3.2.2.联合电子未来汽车电子架构3.2.3.安波福汽车电子架构3.2.4.丰田汽车电子架构3.2.5.华为汽车电子架构 3.智能汽车电子架构 3.1.汽车电子概念及发展 汽车电子是车体汽车电子…

LeetCode146:LRU缓存

leetCode:146. LRU 缓存 题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中&#x…