NOIP 提高 2012 第一轮 第 16 题：已知带权有向图 G 上的所有权值均为正整数，记顶点 u 到顶点 v 的最短路径的

题目

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

答案

C、D

题解

考点定位

本题考「最短路性质（不定项）」,对应大纲 4.3.3 最短路（难度【4】）。

解题过程

• A v₁ 到 v₂ 的最短路径可经过 v₃ ✓（取决于权值）；
• B d(v₁,v₂)=d(v₂,v₁) ✗：有向图不对称；
• C d(v₁,v₃) ≤ d(v₁,v₂)+d(v₂,v₃) ✓ 三角不等式；
• D v₁→v₂→v₃ 是 v₁ 到 v₃ 的最短路 ⇒ d(v₁,v₂)+d(v₂,v₃)=d(v₁,v₃) ✓（子路径最优性）。

答案：C、D。

易错提醒

① 有向图最短路无对称性；② 最短路子路径仍是最短路（剪除引理）——D 是其等价表述。