单源最短路问题
单元最短路问题
通过不同的方式解决单元最短路问题
图，不是树
0 问题描述
单元最短路问题、有向无环图
1 暴力求解
深度优先搜索DFS
广度优先搜索BFS
2 回溯法
深度优先算法，每次回溯的时候进行剪枝操作。
如果此分支没有希望比已经保存的最短路更优。
而且可以从不同的点到达同一个点。保留之前到达这个点的状态，如果最新到达这个点的距离小于之前的距离，则继续向下走，如果大于则放弃并回溯。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Estom的博客！
相关推荐
2022-10-08
04 事务
事务1 简介事务概念事务是数据库操作最近本的单元，逻辑上一组操作，要么都成功，如果有一个失败，所有的都失败。 事务有四大特性ACID 原子性，不可分割 一致性，多个事务看到的数据是一致的 隔离性，多个事务不会产生影响 持久性，可以持久化 准备环境 创建service和dao层的bean（设计代码架构） 实现转账的业务逻辑（开发业务逻辑） 撰写测试用例进行测试（测试代码） 2 事务步骤操作步骤 开启事务操作 进行业务操作，并添加异常处理 没有发生异常，提交事务。 第四部 出现异常事务回滚 Spring事务管理介绍 事务添加到三层结构的service层 在spring进行事务管理操作 声明式事务管理。通过配置实现。 编程式事务管理。需要写代码 生命式事务管理 注解方式 xml配置文件方式 在Spring进行声明式事务管理，底层使用AOP 提供一个接口，代表事务管理。针对不同的框架提供了不同的实现类。 事务管理器 3 基于注解的声明式事务管理步骤 配置事务管理器 12345678910111213141516```2. 在Spring配置文件中开启事...
2020-01-04
1.5 图算法-Prim算法
图算法-Prim算法 目录 图算法-Dijkstra算法 图算法-Floyd算法 图算法-Bellman-Ford算法 图算法-Prim算法 图算法-Kruskal算法 参考文献 https://www.cnblogs.com/ggzhangxiaochao/p/9070873.html 1 问题分析 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。 主要思想是基于顶点的贪心思想。 2 算法原理 输入：一个加权连通图，其中顶点集合为V，边集合为E； 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 重复下列操作，直到Vnew = V： 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任...
2021-12-24
lvreduce
lvreduce收缩逻辑卷空间 补充说明lvreduce命令 用于减少LVM逻辑卷占用的空间大小。使用lvreduce命令收缩逻辑卷的空间大小有可能会删除逻辑卷上已有的数据，所以在操作前必须进行确认。 语法1lvreduce(选项)(参数) 选项12-L：指定逻辑卷的大小，单位为“kKmMgGtT”字节；-l：指定逻辑卷的大小（LE数）。 参数逻辑卷：指定要操作的逻辑卷对应的设备文件。 实例使用lvreduce命令减少指定的逻辑卷的空间大小。在命令行中输入下面的命令： 1[root@localhost ~]# lvreduce -L -50M /dev/vg1000/lvol0 #将逻辑卷的空间大小减少50M 输出信息如下： 1234......省略部分输出内容...... Do you really want to reduce lvol0? [y/n]: y #确认操作 Reducing logical volume lvol0 to 252.00 MB Logical volume lvol0 successfully resized
2020-09-26
legend_demo
图例（Legend）演示在Matplotlib中绘制图例。 在Matplotlib中有很多方法可以创建和自定义图例。 下面我们将展示一些如何操作的示例。 首先，我们将展示如何为特定线条制作图例。 1234567891011121314151617181920212223import matplotlib.pyplot as pltimport matplotlib.collections as mcolfrom matplotlib.legend_handler import HandlerLineCollection, HandlerTuplefrom matplotlib.lines import Line2Dimport numpy as npt1 = np.arange(0.0, 2.0, 0.1)t2 = np.arange(0.0, 2.0, 0.01)fig, ax = plt.subplots()# note that plot returns a list of lines. The "l1, = plot" usage# extracts...
2020-10-13
16_Unsupervised Learning Introduction
Unsupervised Learning: IntroductionUnsupervised Learning无监督学习(Unsupervised Learning)可以分为两种： 化繁为简 聚类(Clustering) 降维(Dimension Reduction) 无中生有(Generation) 对于无监督学习(Unsupervised Learning)来说，我们通常只会拥有$(x,\hat y)$中的$x$或$\hat y$，其中： 化繁为简就是把复杂的input变成比较简单的output，比如把一大堆没有打上label的树图片转变为一棵抽象的树，此时training data只有input $x$，而没有output $\hat y$ 无中生有就是随机给function一个数字，它就会生成不同的图像，此时training data没有input $x$，而只有output $\hat y$ ClusteringIntroduction聚类，顾名思义，就是把相近的样本划分为同一类，比如对下面这些没有标签的image进行分类，手动打上cluster 1、...
2021-06-16
5 多人协作
5 多人协作通过远程库的push和pull操作实现夺人合作 推送分支或分支内容 当从远程库进行克隆的时候，实际上已经将本地master分支和远程的master分支进行乐关联。 1git remote [-v] 可以显示与远程库关联的信息 1git push origin master 推送分支，吧分支上的所有本地内容提交到远程库中的相同分支当中。 哪些分支需要推送 mater分支是主分支，需要实时推送 dev是开发分支，所有成员都要在上面工作。也需要与远程同步。 bug分支只需要在本地修复bug，没有必要推送到远程。 feature分支，可以不用推送到远程。单人开发不用，夺人开发要推送到远程。 抓取分支或者分支的内容1git checkout -b dev origin/dev 可以用来抓取远程分支dev，这样会建立一个本地的本地的dev分支与远程的dev分支进行关联，可以直接实现dev分支的控制（push） 1git pull \<remote\> \<branch\> 如果Git push失败，说明，当前的版本不是最新的版本。git pull可...
