GESP 8级客观题｜单源最短路｜课后作业

考试频率：低频。本卷共 3 题。

1. 使用邻接表和优先队列实现 Dijkstra，常见时间复杂度为（ ）。

   {{ select(1) }}

• $O(n^2)$
• $O((n+m)\log n)$
• $O(2^n)$
• $O(nm^2)$

2. 最短路算法中的“松弛”操作是指（ ）。

   {{ select(2) }}

• 删除一条边
• 尝试用经过当前边的新路径更新距离
• 把所有边权变为 1
• 给顶点重新编号

3. 若图中存在负权边但不存在负环，以下更适合求单源最短路的是（ ）。

   {{ select(3) }}

• 经典 Dijkstra
• Bellman-Ford
• Kruskal
• Prim