无权图的单源最短路算法

xianshenglu
  • 4.4k

如图

image.png

源课程链接

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

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

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

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

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏