NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 16 题

已知带权有向图 $G$ 上的所有权值均为正整数，记顶点 $u$ 到顶点 $v$ 的最短路径的权值为 $d(u, v)$。若 $v_1, v_2, v_3, v_4, v_5$ 是图 $G$ 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（ ）。

拿到题先想‘最短路’的定义和性质：权值全为正意味着最优解不可能绕圈；三角不等式和最优子结构是两条铁律，把这两个点拎出来，选项就一目了然。

很多学生看到‘环’就下意识觉得可能经过，忘了题目强调所有权值为正整数。正权图中，只要路径里有个环，把环拆掉得到的新路径权值一定更小，那原来的路径就不是最短了，所以A肯定错。还有学生容易混淆有向图和无向图，觉得两点间距离应该相等，其实有向图里v1到v2和v2到v1完全是两条不同的路，B自然不对。C和D是课本里最核心的两个性质，只要记住‘最短路满足三角不等式’和‘最短路的子路径仍是最短路’，就不会掉坑里。

考点与概念

这道题考查的是最短路径的两个基本性质： 1. 三角不等式：对于任意三点 u, v, w，有 d(u, w) ≤ d(u, v) + d(v, w)。 2. 最优子结构：如果一条路径是最短的，那么它的任意子路径也一定是最短的。

命题人怎么挖坑

命题人特别喜欢在‘环’和‘方向’上做文章。

• 对于A选项，学生容易凭直觉认为‘绕一圈可能更近’，但题目特意强调‘所有权值为正整数’，这就是在提示：正权图中，任何包含环的路径都可以去掉环得到更短的路径，因此最短路径绝对不可能包含环。
• 对于B选项，学生容易把有向图当成无向图，误以为两点间距离是对称的。其实有向图中 v1→v2 和 v2→v1 是两条完全独立的路径，距离不一定相等。

思考心法与逐项分析

拿到题，先快速过一遍最短路定义，再逐个选项对位：

• A：若最短路径含环，去环后路径更短，矛盾。故A错。
• B：有向图无对称性，d(v1,v2)与d(v2,v1)没有必然相等关系。故B错。
• C：这就是三角不等式。从 v1 到 v3 可以走 v1→v2→v3，这条路的长度是 d(v1,v2)+d(v2,v3)；而 d(v1,v3) 是所有路径中的最小值，自然不大于这条具体路径。故C正确。
• D：这是最优子结构。已知 v1→v2→v3→v4→v5 是 v1 到 v5 的最短路径，那么其中任意一段，比如 v2→v3→v4，一定是 v2 到 v4 的最短路径。否则，如果存在更短的 v2→v4 路径，把它拼上 v1→v2 和 v4→v5，就会得到一条比原路径更短的 v1→v5 路径，与前提矛盾。故D正确。

避坑提醒

最容易错的是A和B。记住：正权图里最短路径不含环，有向图距离不对称。只要守住这两条线，C和D这种性质题基本不会翻车。

考频与趋势

最短路径是图论中的高频考点，题库共考过 35 题，覆盖 7 个考试级别（2008-2026）。逐年分布：2008年2题、2011年1题、2012年1题、2013年1题、2014年1题、2015年2题、2016年1题、2018年1题、2019年1题、2020年1题、2021年1题、2024年6题、2025年7题、2026年7题、2题（null年）。分赛事：GESP 八级17题、NOIP 提高组 初赛9题、CSP 提高级5题、GESP 六级1题、NOIP 普及组 初赛1题、GESP 五级1题、GESP 七级1题。

从数据看，2024-2026 三年在最短路径上的考题数量明显上升（2024年6题、2025年7题、2026年7题），说明该知识点在近年命题中愈发受重视，尤其是竞赛级别（NOIP 提高组、GESP 八级）的考查频率较高。

预测

基于上述趋势，可以合理预测：未来命题仍会围绕最短路的核心性质（三角不等式、最优子结构、正权无环等）出题，形式可能继续以单选或多选判断为主，难度上可能会结合具体算法（如 Dijkstra、SPFA）的适用条件进行综合考查。暂无足够依据预测更具体的题目形式或数值范围。