无权图的单源最短路算法

Question

如图

源课程链接

私以为，复杂度应该是 O(|V|*|E|)，因为里外两层循环啊，为什么图中认为是 O(|V|+|E|)

Answer 1

对于这段代码来说，图中每个点和边最坏情况对会被访问一次，因此时间是 v + e.

如果是 v * e，那么相当于对于每一个点都会 check 所有边（即便是和当前点不相连），这是不可能的。

Answer 2

外层循环用来遍历所有点，内层循环用来遍历所有边。如果是V*E，那就成了对于每个点都处理每条边，显然不是所有的边都连接在点上的。