当前位置: 首页 > news >正文

01bfs 对 dij最短路的优化,以及一些易错点

01bfs就是加了个deque来进行速度的优化,避免多次重复访问节点
但是01bfs我一般会加一个inque来判断是否重复加入

于是inque的写法上就出错了
1:使用inque之后,最好不要在deque里存当前的值,因为这个值只会被放入一次,可能不是最优的一次
于是只用存当前节点,值就用当前节点转移过去即可

2:deque用来代替优先队列,但是并不能在任何图中使用,只有大量的边权为0的图中,此边权可能是抽象的

3:可以进行扩展,比如常数种边权的情况。

——————————————————————————————————————————————————————————————————————————————————————————————————————————
更新值在内层循环中,所以因为inque存在,所以外层循环不要判断权值并且continue。
注意inque更新的时机,如果没有加入,但是更新了,会错

http://www.rkmt.cn/news/52.html

相关文章:

  • 数据结构与算法-21.堆-排序
  • 学习笔记-安全概述
  • Adobe Animate CC2018安装包下载与安装教程
  • 完整教程:以数据与自动化驱动实验室变革:智能化管理整体规划
  • 软件工程第一次作业
  • Windows11新系统激活设置PIN码步骤转圈
  • Elasticsearch
  • MySQL单表查询DQL
  • PyQt5 之QMenu菜单栏
  • 事半功倍是蠢蛋51 大上黑白屏反色
  • Linux 启动耗时优化 1s 内启动(RK3588 平台)
  • 周总结报告5
  • 使用模拟库进行测试的意义是什么?