GESP 八级 · GESP 八级样题（C++ 组） 第 23 题

如果一个图中所有边的权重都为正数，则 Floyd 算法可以求出该图中任意两个顶点间的最短路径。（ ）

这题考 Floyd 算法的适用条件。拿到题先想：Floyd 是动态规划求全源最短路，核心公式 d[i][j]=min(d[i][j],d[i][k]+d[k][j])，它不依赖边权正负，只要求图内无负环。题目说所有边权重为正，自然无负环，所以能正确求出任意两点最短路径，选 A。

学生最容易把 Dijkstra 的「非负边权」要求错误迁移到 Floyd 上，误以为 Floyd 也不能处理负权边；或者死记「Floyd 用于所有图的最短路」而不理解其原理，看到「正数」就犹豫是否包含零。命题人爱在这里挖坑，利用考生对算法适用条件的记忆混淆，特别是把 Dijkstra 的限制套用到 Floyd 上。另外，考生可能纠结「可以求出」是否包含不连通情况，其实 Floyd 对不连通图返回无穷大也是正确输出，但题目已限定正权边，无需担心。

【考点】Floyd 算法｜最短路径｜图论

1. 考纲定位

GESP 八级图论模块核心算法。命题人卡住绝大多数考生的「算法适用条件」记忆——把 Dijkstra 的「非负边权」要求错误迁移到 Floyd 上，这是八级考生最典型的思维定势。