单选题
适中
#24838
对于含n个顶点( n>=2)的连通加权有向图,若图中不存在负权环,则任意两点之间的最短路径(简单路径)最多包含( )条边。
对于含n个顶点( n>=2)的连通加权有向图,若图中不存在负权环,则任意两点之间的最短路径(简单路径)最多包含( )条边。
答案与解析
正确答案:B
解析
在含 n 个顶点的连通加权有向图中,若不存在负权环,则任意两点间的最短路径必为简单路径。简单路径的定义是不重复经过任何顶点的路径。路径中每条边连接两个不同顶点,因此路径上最多可经过 n 个顶点。若起点为 u,终点为 v,且路径经过所有顶点,则路径中最多包含 n-1 条边,因为从第一个顶点到第 n 个顶点需要 n-1 次转移。若路径包含 n 或更多条边,则至少有一个顶点被重复访问,违背简单路径的定义。因此,最短路径所含边数不可能超过 n-1 条。