题目
对于含 $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 的陷阱在于忽略"不存在负权环"这一关键条件。若条件改为允许负权环,最短路径边数将无法确定。刷到此类题时,先确认是否有"简单路径""无负权环"等限制,再结合顶点数判断边数上界。
同考点真题
- 第 13 题· NOIP 2015 提高组初赛试题 · 答案 D看解析 →
- 第 28 题· NOIP 2015 提高组初赛试题 · 答案 v=-1dist[i]<dist[v]dist[v]>dist[i]dist[i]<=dist[v]dist[v]>=dist[i]v=iused[v]=1dist[v]+w[v][i]<dist[i]dist[i]>dist[v]+w[v][i]dist[v]+w[v][i]<=dist[i]dist[i]>=dist[v]+w[v][i]看解析 →
- 第 28 题· NOIP 2016 提高组初赛试题 · 答案 dist[1]=0dist[x]+weight[j]<dist[point[j]]weight[j]+dist[x]<dist[point[j]]dist[point[j]]>weight[j]+dist[x]dist[point[j]]>dist[x]+weight[j]visit[x]=0weight[j]+dist[x]==dist[point[j]]dist[x]+weight[j]==dist[point[j]]visit[point[j]]=1看解析 →
- 第 28 题· NOIP 2017 提高组初赛试题 · 答案 degree[b]=degree[b]+1degree[b]++++degree[b]degree[i]==0!degree[i]degree[i]=degree[i]-1degree[i]----degree[i]head=head+1head++++headans<len[a]len[a]>ans看解析 →
- 第 13 题· CSP 2019 提高级第一轮 · 答案 B看解析 →