问个关于最短路的问题
  • 板块灌水区
  • 楼主_0o0_
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/10/2 13:04
  • 上次更新2024/10/2 16:28:40
查看原帖
问个关于最短路的问题
671610
_0o0_楼主2024/10/2 13:04

优化dijkstra算法里的vis数组我试着删除了一下,发现正确性不变但是复杂度上来了

我想:算法过程中,每次从堆里面拿出dis最小的那一个后,其dis值是不会再变了的(没有负权边),那么在其他点松弛的时候,这个点应该是不会再被更新了的,也就不会进入堆里,那vis数组是不是也就可有可无

但是一试发现不对,求大佬解释一下

2024/10/2 13:04
加载中...