首页 > 编程语言 >算法笔记

算法笔记

时间:2023-11-28 22:23:05浏览次数:35  
标签:Vi 城市 MAXV 笔记 算法 road Vj 起点

图的算法

Dijkstra算法:(净化被黑暗能量污染的城市) 求图的单源最短距离,给出图G(V,E) (精灵城市图)和起点城市O (Origin),设置一个存放已经被光明之力净化的城市集合S,现在要从起点O出发,开放所有与起点O相连的road,以最短路径去往各城市进行净化,每次从V-S集合(未被净化的城市)中选出一个与起点城市O距离最近的城市Vi,选出Vi后就开放所有与Vi相连的road,从这些road计算看是否有可以优化起点城市到某城市Vj的最短路径(起点到Vi的最短路径距离+Vi—>Vj的road长度 是否小于 Vj 原本所记录的最短距离)(每个Vj 上记录了当前情况下起点到Vi的最短距离),如果小于则更新Vj上的数据,就这样每次从V-S集合(未被净化的城市)中选出一个与起点城市O距离最近的城市Vi 然后根据其road进行计算并优化,直到V-S集合为空。 有几个城市就设置循环几次,最终求出了起点O到所有城市的最短距离

可以用邻接矩阵和邻接表来实现该伪代码,邻接矩阵需要枚举所有顶点来查看Vj 是否可由Vi 到达,邻接表可以直接得到Vi 所有能到达的Vj

只能应对所有边权都是非负数的情况,边权出现负数最好适用SPFA算法

最外层for 循环n次是确保所有的节点都有被遍历到

找出最小的d[u]也要一个for循环n次,才能轮询找出最小值

优化d[u]也要一个for循环n次,确保能让所有的d[ ]都计算是否可以优化

**最短路径 ** :可以设置一个pre[v]来记录V节点的上一个节点,在每个优化d[v]后面加上pre[v]=u即可,可以通过递归将该路径输出

数组初始化一个特定数时用G[MAXV] [MAXV] ={INF}和 d[MAXV] = {INF}是不行的,无法全部初始化,要使用 fill (G[0],G[0]+MAXV*MAXV,INF)函数才行,fill (d,d+MAXV,INF)函数进行初始化。

总结

Dijkstra算法算是贪心思想实现的,首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

标签:Vi,城市,MAXV,笔记,算法,road,Vj,起点
From: https://www.cnblogs.com/ywx1207/p/17863257.html

相关文章

  • 聪明办法学python-11.27——11.29笔记打卡
    一、python中条件语句的应用总体代码结构为:ifTrue:dosomethingelse:doother简单描述为“True”为条件,当条件为真的时候,执行“dosomething”,否则就执行“doother”。例如:任务:实现一个函数,返......
  • 应用密码学复习笔记
    1.翻译保密性confidentiality保密性(Confidentiality):这个术语包含了两个相关的概念:数据保密性:确保隐私或者秘密信息不向非授权者泄露,也不被非授权者所使用。隐私性:确保个人能够控制或确定与其自身相关的哪些信息是可以被收集、被保存的,这些信息可以由谁来公开以及向谁公开.完......
  • VisionPro学习笔记(5)——极轴展开工具PolarUnwrapTool
    如果需要了解其他图像处理的文章,请移步小编的GitHub地址传送门:请点击我如果点击有误:https://github.com/LeBron-Jian/ComputerVisionPracticeVisionPro有很多的示例和算子,这里展示一个基础的算子PolarUnwrapTool。我自己的笔记不会按照顺序一一展示出来的,也许那......
  • 有向图求强连通分量的几种算法
    概要本文介绍了kosaraju,tarjan算法求强连通分量概念有一个有向图G,有几个概念强连通若图中有两个点u和v,他们能互相到达,则称他们强连通强连通图若是G中任意2个点都可以互相到达,则称G是一个强连通图强连通分量有向非强连通图的极大强连通子图(可以有很多个)完全......
  • 【Python爬虫】第11篇:Mongodb数据库进阶使用。从0到scrapy高手笔记(附代码,可自取)
    本文主要学习一下关于爬虫的相关前置知识和一些理论性的知识,通过本文我们能够知道什么是爬虫,都有那些分类,爬虫能干什么等,同时还会站在爬虫的角度复习一下http协议。全套笔记和代码自取地址:请移步这里感兴趣的小伙伴可以自取哦,欢迎大家点赞转发~共8章,37子模块Mongodb数......
  • 聪明办法学python第3次笔记
    条件ifelse语句if条件:执行行为else:执行行为elif语句:等同与c语言中的elsei语句ifx>10:print()elifx=10:print(2)else:print(3)ifelse推导式print(nif(n>0)else-n)match-case语句:等同于c语言中的switch-casem=map(int(),input())match......
  • 《信息安全系统设计与实现》第十三周学习笔记
    《信息安全系统设计与实现》第十三周学习笔记第十四章MySQL数据库系统MySQL简介MySQL是一个关系数据库系统在关系数据库中,在关系数据库中,数据存储在表中。每个表由多个行和列组成。表中的数据相互关联。表也可能与其他表有关联。关系结构使得可在表上运行查询来检索信息并修......
  • 学习笔记4
    用户与权限管理1.用户与用户组用户的操作使用管理员账户或sodo提权创建用户:useradd-m用户名-m: 自动建立用户的登入目录-uUID: 指定UID,这个UID必须是大于等于500,并没有其他用户占用的UID-gGID/GROUPNAME: 指定默认组,可以是GID或者GROUPNAME,同样也必须真实存在-......
  • 学习笔记5
    命令查找1.命令搜索whereis 搜索命令的位置和帮助文档的位置which 搜索位置和命令的别名2.find类似于Windows中的搜索文件find[-path]-options‘文件’path:要查找的目录,默认是当前目录option:-name 按文件名的某种规则的查找-type 按文件类型查找f普通文件......
  • 学习笔记6
    文本传输1.管道将程序或命令的输出作为另一个程序或者命令的输入,就是用管道来进行完成管道把一系列的命令链接起来管道符:|命令:xargs2.输入重定向在Linux系统中,所有的都是文件或文件夹,终端也是文件输入重定向指的是把命令或者程序的标准输入重定向到指定的文件中,输入可以不......