关于图论中的最短路径算法,下列说法中严格正确的是( )。
A:Dijkstra 算法能够高效处理包含负权边的有向图。
B:Floyd 算法可以求出任意两点间的最短路径,且允许图中存在负权边(但不能有负权环)。
C:单源最短路径算法无法用于无向图,无向图只能通过 BFS 求解。
D:Dijkstra 算法的每一步必定从当前未访问的节点中,选取距离起始点最远的节点进行松弛操作。
正确答案:B
答案解析
Dijkstra算法基于贪心策略,每次选择当前距离源点最近的未访问节点进行扩展,仅适用于非负权边图。Floyd算法通过动态规划计算所有顶点对之间的最短路径,可处理负权边但要求图中无负权环。单源最短路径算法适用于有向与无向图,无向图中边可视为双向有向边,BFS仅适用于无权图或权值相等的图。Dijkstra算法每步选取距离起始点最近的未访问节点,而非最远节点,松弛操作更新邻接节点的最短距离估计值。
试卷来源:202603 CCF-GESP编程能力等级认证C++八级真题