GESP 2024年6月 C++八级判断题第5题

Question

在 v 顶点 e 边的带权连通简单有向图上用 Dijkstra 求最短路，复杂度为 O(v²)，可优化至 O(e+v·log v)。

Accepted Answer

答案：正确（√）。正确。朴素 Dijkstra 为 O(v²)，用优先队列（堆）优化后约为 O((v+e)·log v)，即 O(e+v·log v)。

GESP 2024年6月 C++八级 判断题 第5题