12/12每日总结

时间：2023-12-12 21:00:46浏览次数：32

标签：总结 12 中转每日路径最短算法顶点 Vo

最短路径

BFS求无权图的单源最短路径

简介

直接进行广度优先遍历

使用两个数组，一个记录最短路径值，一个记录到这个顶点的直接前驱

只能用无权图

迪杰斯特拉算法

简介

dijkstra算法是一种一步一步找出最短路径的方法，核心思路就是从初始点开始，一步一步从已确定路径中选取最短的路径作为新的最短路径，并加入新已确定顶点，然后执行多次

实现

我们选用三个数组，分别是标记各顶点是否已找到最短路径的finals，最短路径长度的dist，以及记录路径上的前驱的path

12/12每日总结_数组

12/12每日总结_最短路径_02

也就是我们每次将可到达的结点找出来，从可获取路径中找到最短路径，并将其前驱记录，标记出结点

时间复杂度为O(n^2)即O(|V|^2)

如果用于负权值带权图，则迪杰斯特拉算法可能会失效

弗洛伊德算法

简介

Floyd算法是求出每一对顶点之间的最短路径使用动态规划思想，将问题的求解分为多个阶段

对于个顶点的图G,求任意一对顶点Vi一>Vj之间的最短路径可分为如下几个阶段：#初始：不允许在其他顶点中转，最短路径是？ #0:若允许在Vo中转，最短路径是？ #1:若允许在Vo、V1中转，最短路径是？ #2:若允许在Vo、V1、V2中转，最短路径是？ ...... #n-1:若允许在Vo、V1、V2.Vn-1中转，最短路径是？

12/12每日总结_最短路径_03

12/12每日总结_最短路径_04

例如这样，左边的矩阵就是初始时，不中转获得的个顶点建最短路径长度，右边的矩阵是初始时中转点的记录，因为不中转，所以是-1

若允许在V0中转，则新加一

12/12每日总结_数组_05

12/12每日总结_数组_06

编辑

如此经历n轮递推

woc，大道至简，本身以为是只有一个节点做中转的情况，但是仔细一想，它并不是单源的算法，而是点到点的算法，并且也从来不是每次加一个这么简单，他是考虑了所有的结点

就好比是需要经过 0 2 4 6才能到这个点，在查找时0->2是最小值不需要中转,0->4是经过2的中转，0到6是经过4的中转，但是到4的中转前已经中转过2了,所以这种算法已经考虑了所有的情况

DAG

简介

有向无环图简称DAG 图

DAG描述表达式

12/12每日总结_结点_07

12/12每日总结_结点_08

相同部分可以合并

12/12每日总结_最短路径_09

12/12每日总结_最短路径_10

节省存储空间

顶点中不能出现重复的操作数，标出来各个运算符的生效顺序，注意分层

标签：总结,12,中转,每日,路径,最短,算法,顶点,Vo
From： https://blog.51cto.com/u_16196891/8791168

数仓项目总结
数仓项目总结一、数据采集数据从哪里来的？一般在实际开发中，是业务开发端在业务系统程序中，植入一些收集事件数据的SDK(工具代码),进行各种事件数据的收集，埋点数据可以植入到业务系统的前端程序或者后端程序中。我们作为大数据开发，只需要提出数据埋点需求，对具体实现技术仅作基本了......
Solution Set 2023.12.12
ABC332GNotTooManyBalls可以转化为最大流模型，设节点\(x_i\)代表第\(i\)种球，\(y_j\)代表第\(j\)个盒子。考虑如下建边方案：\(S\rightarrowx_i\)，容量为\(A_i\)\(x_i\rightarrowy_j\)，容量为\(i\timesk\)\(y_j\rightarrowT\)，容量为\(B_j\)可以发现该网络......
CF1253F Cheap Robot
题意给定一个图，走过一条边的花费为权值，其中有\(k\)个充电点。你需要确定一个电量的上限，使得满足从\(a\)走到\(b\)。Sol先对于每个点求出她走到充电点最近的距离，用\(dij\)随便跑跑。考虑从\(a\tob\)一条边的贡献。设当前的电量上限为\(c\)。可得：\[c-dis_a\ge......
每日导数5
找出相同结构设函数\(f\left(x\right)=\mathrm{e}^x-1-ax\).\((1)\)若\(x\geq0\),\(f\left(x\right)\geq0\),求\(a\)的取值范围;\((2)\)若\(x>0\)且\(m\geq1\),证明：\(f\left(x\right)\geq\dfrac{x^2}{\ln\left(x+m\right)}-ax\).(1)因为\(f\left(x\ri......
关于Rust的简单总结(一)
0.前言这是一个关于Rust的简单总结。(待续)资料学习网址：学习Rust-Rust程序设计语言(rust-lang.org)官网：Rust程序设计语言(rust-lang.org)Rust介绍[[Rust]]程序设计语言的本质实际在于赋能（empowerment）：无论你现在编写的是何种代码，Rust能让你在更为广泛的编程......
项目经理的年终总结没写好，一年全白干
项目经理年终吐槽大会：又到年底了，办公室的项目经理们好不容易能聚在一起，大家在交流工作时，对这一年的工作状态简要吐槽了几句。每一句都堪称经典，但无不透露出各种心酸。a) 项目经理小王：感情状态——继续单身，根本没空谈恋爱；身材体重——过劳肥。b) 项目经理小刘：每......
2023-12-12 双十二思考借钱给steve的事
2023-12-12 2014年投资了3.8W合伙成立半山腰。这个事情也怪我当初，我看Sw总要创业，做的事情又是有经验的，投资一点，以后赚了就跟着赚一点，亏了我也认栽。从一开始，就没有想过投资2~3万，要他回报给我2~300万。能赚个10几万，我觉得就很不错了。后面就很多年里，应该有7~8年，每年都问我......
12.12邻接表存储实现图的深度优先遍历（c++）
今天学习了数据结构中的邻接表存储实现图的深度优先遍历，其中让我受益匪浅，以下是我的解题思路。编写程序，实现由邻接表存储实现无向图的深度优先搜索遍历的功能。顶点为字符型。输入格式:第一行输入顶点个数及边的个数，第二行依次输入各顶点，第三行开始依次输入边的两个顶点，用空格......
12.11 迪杰斯特拉方法实现最短路径（c++）
今天通过自主学习，，对数据结构中的迪杰斯特拉方法实现最短路径进行了深造，让我学会了很多新的东西。首先是问题描述：用迪杰斯特拉算法实现有向网的最短路径输入格式:第一行输入有向网的顶点和边数，第二行输入各顶点值，用空格间隔，第三行开始输入各条边的两个点的及边上的权值，用空......
2023年12月陕西广州/深圳软考高级信息系统项目管理师招生简章
信息系统项目管理师是全国计算机技术与软件专业技术资格（水平）考试（简称软考）项目之一，是由国家人力资源和社会保障部、工业和信息化部共同组织的国家级考试，既属于国家职业资格考试，又是职称资格考试。信息系统项目管理师，属于软考三个级别中的“高级”。【报考要求】不设学历与资历条......