优化dijkstra算法里的vis数组我试着删除了一下,发现正确性不变但是复杂度上来了
我想:算法过程中,每次从堆里面拿出dis最小的那一个后,其dis值是不会再变了的(没有负权边),那么在其他点松弛的时候,这个点应该是不会再被更新了的,也就不会进入堆里,那vis数组是不是也就可有可无
但是一试发现不对,求大佬解释一下