GESP 八级 · GESP 202603 C++ 八级 第 7 题

选择题 · 答案 B · 考点:图论算法、算法

← 整套速查表 GESP 八级 全部真题

题目

对于含 $n$ 个顶点 ($n \ge 2$) 的连通加权有向图,若图中不存在负权环,则任意两点之间的最短路径(简单路径)最多包含( )条边。

答案:B

考点

图论算法算法

解题思维

单源最短路:Dijkstra(无负权,O(mlog n))、SPFA/Bellman-Ford(可负权,检测负环)。全源:Floyd(O(n³))。

常见错误

Dijkstra不能处理负权边。有负权边用Bellman-Ford或SPFA。有负环时最短路不存在(可无限缩小)。

详细解析(节选)

【考点】图论|最短路径算法|简单路径性质

本题核心在于理解"简单路径"的定义。简单路径要求路径中每个顶点最多出现一次,因此路径边数必然少于顶点数。图中有 n 个顶点,任意两点间的最短路径一定是简单路径,所以最多包含 n-1 条边。命题人设置"不存在负权环"的条件,就是为了排除"绕环无限缩短"的可能性,确保最短路径一定简单。选项 A 和 C 的陷阱在于混淆"顶点数"与"边数"的关系,选项 D 的陷阱在于忽略"不存在负权环"这一关键条件。若条件改为允许负权环,最短路径边数将无法确定。刷到此类题时,先确认是否有"简单路径""无负权环"等限制,再结合顶点数判断边数上界。

同考点真题

在 OI伴学 里做这道题
登录后可计时作答、查看完整六段式解析,并按你的错题自动生成同类练习。
去刷题先做一次 AI 学情诊断