判断题 偏易
#21044

在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径,时间复杂度为O(v2),可进一步优化至O(e+vlog(v))。

在一个包含 v 个顶点、 e 条边的带权连通简单有向图上使用Dijkstra算法求最短路径,时间复杂度为O(v2),可进一步优化至O(e+vlog(v))。

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析

暴力枚举每个点,时间复杂度是O(v2);用优先队列每次找到距离最短的点,优先队列时间复杂度是O(logn),每个点和边都访问一次,所以时间复杂度是O(e+vlogv)。