软考题库
软件设计师 · 高频练习

要求所有顶点对最短路径且允许负权边时，为什么常选 Floyd？

中级 单选题 第 921 题 中等 软件设计师Floyd最短路径动态规划负权边
内容整理：软考题库编辑部 最近更新：
题目

某带权有向图可能包含负权边，但不存在负权回路。现在需要求任意两个顶点之间的最短路径。较合适的算法是（）。

A Floyd 算法
B 标准 Dijkstra 算法从任意一个点只运行一次
C Prim 最小生成树算法
D 仅做一次拓扑排序
题目类型：原创高频练习题 用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。
正确答案
A
答案解析

Floyd-Warshall 通过动态规划逐步允许更多中间顶点，可求所有顶点对最短路径，并能处理负权边；前提是不存在可达的负权回路。

选项分析

A

正确。Floyd 适合稠密图的所有顶点对最短路径，并允许无负环的负权边。

B

错误。单次 Dijkstra 只解决一个源点，且标准算法依赖非负边。

C

错误。Prim 最小化的是生成树总边权，不保证任意顶点对路径最短。

D

错误。拓扑排序只给出偏序，不能单独计算一般带权图最短距离。

本题为什么容易错

“权值最小”几个字容易让人把最短路径和最小生成树混在一起。一个优化路径长度，一个优化连接所有顶点的总成本，目标函数不同。

先看结论

简短答案

要求所有顶点对最短路径且允许负权边时，为什么常选 Floyd，正确答案是 A（Floyd 算法）。Floyd-Warshall 通过动态规划逐步允许更多中间顶点，可求所有顶点对最短路径，并能处理负权边；前提是不存在可达的负权回路。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
Floyd 算法 本题正确答案 正确。Floyd 适合稠密图的所有顶点对最短路径，并允许无负环的负权边。 看到题干核心场景时优先联想到它
标准 Dijkstra 算法从任意一个点只运行一次 本题干扰项 错误。单次 Dijkstra 只解决一个源点，且标准算法依赖非负边。 看到该词不要急着选，先判断是否真正解决题干问题
Prim 最小生成树算法 本题干扰项 错误。Prim 最小化的是生成树总边权，不保证任意顶点对路径最短。 看到该词不要急着选，先判断是否真正解决题干问题
仅做一次拓扑排序 本题干扰项 错误。拓扑排序只给出偏序，不能单独计算一般带权图最短距离。 看到该词不要急着选，先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • 标准 Dijkstra 算法从任意一个点只运行一次：错误。单次 Dijkstra 只解决一个源点，且标准算法依赖非负边。
  • Prim 最小生成树算法：错误。Prim 最小化的是生成树总边权，不保证任意顶点对路径最短。
  • 仅做一次拓扑排序：错误。拓扑排序只给出偏序，不能单独计算一般带权图最短距离。
复习

知识点详解

Floyd-Warshall 的核心是动态规划：第 k 阶段比较原路径 i→j 与经过 k 的路径 i→k→j。若最终出现 d[i][i]<0，通常说明存在负权回路。顶点很多且图稀疏时，实际工程会结合 Johnson 等算法，但软考常重点比较 Floyd、Dijkstra 和 Bellman-Ford 的适用边界。

备考速记

所有点对、允许负边、没有负环，优先想到 Floyd。

Floyd 在负权边场景中的作用

Floyd在本题中的核心价值，是解决“某带权有向图可能包含负权边，但不存在负权回路。现在需要求任意两个顶点之间的最短路径。较合适的算法是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 根据图类型和需求选择最短路径算法。
  • 使用 Floyd 递推式更新某一轮距离矩阵。
Floyd 在软件设计师软考中的考法

软考选择题通常不会只考概念定义，还会把Floyd放到负权边场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。

解题思路

题干给了两个信号：一是“任意两个顶点”，说明要全源；二是“可能有负边但无负环”。Floyd 正好对应这组条件。它用 `d[i][j]=min(d[i][j], d[i][k]+d[k][j])` 反复放宽中间点。标准 Dijkstra 不接受负权边，而且从一个起点只跑一次也得不到所有点对。

考点定位

先看求单源还是全源，再看边权限制。标准 Dijkstra 要求非负边；Prim 求的是无向连通图的最小生成树，不是最短路径矩阵。

易错提醒

  • Floyd 更新时把上一轮尚未稳定的数据覆盖顺序写错。
  • 认为有负边就一定没有最短路径；真正致命的是可达负环。
  • 忽略 O(n^3) 时间和 O(n^2) 空间成本。

备考提示

  • 算法选择先做三问：单源还是全源、边权能否为负、图是否为 DAG。
  • 手算 Floyd 时把 k 当作允许使用的中间顶点阶段。

你可能还想了解

  • Floyd 为什么能处理负权边？
  • 负权边和负权回路有什么区别？
  • 最短路径和最小生成树为什么不是一回事？

本文小结

题目要求所有顶点对最短路径，并允许负权边但没有负环，Floyd与条件匹配。标准Dijkstra要求非负边且单次只解一个源点，Prim解决的则是最小生成树。