无权图的单源最短路算法

xianshenglu
  • 4.4k

如图

image.png

源课程链接

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

回复
阅读 432
2 个回答
✓ 已被采纳

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

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

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

宣传栏