NOIP 普及组初赛 · NOIP 2014 普及组初赛试题 第 22 题

如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是__。 

别急着套算法，这题图太简单，直接拿计算器按计算器。数清每条路加起来，比一比谁最小，这就是最短路径的朴素解法。

最容易掉进的坑是看错数字或者漏算某条边，比如把 A 到 C 的 3 看成别的数，或者忘了 C 到 E 的 8。还有学生可能会想当然地以为最短路径一定经过某个中间点，结果绕远了。记得，最短路径就是所有可能路径里加起来最小的那个，别被图里的其他数字干扰了。

这道题考查的是最短路径的基本概念。在图中，每条边上的数字代表该边的长度，我们需要找到从起点 A 到终点 E 的所有可能路径，计算每条路径的总长度，然后取其中的最小值。这其实就是 Dijkstra 算法最原始、最朴素的形式——因为边数很少，直接枚举所有路径是最稳妥的做法。命题人喜欢用这种简单的图来考察学生是否真的理解‘最短路径’的含义，而不是死记硬背算法步骤。拿到题先别想什么复杂算法，直接从 A 出发，看看有哪些路能通到 E。A 到 E 只有两条路：一条是 A→C→E，另一条是 A→D→E。我们分别算一下：A→C 是 3，C→E 是 8，加起来就是 11；A→D 是 6，D→E 是 5，加起来是 11。咦，两条路都是 11？那最短距离就是 11。这里要注意，有些同学可能会漏掉某条边，或者把数字看错，比如把 C→E 看成 9，那就会算成 12，就错了。所以一定要仔细核对每个数字。另外，虽然 Dijkstra 算法可以处理更复杂的图，但在这种只有几条边的情况下，直接枚举是最快最不容易出错的方法。从考频趋势来看，这类基础最短路径题在 NOIP 普及组初赛中出现频率较高，尤其是结合简单图的计算，是每年必考的知识点。未来可能还会继续以这种形式出现，或者稍微增加一点干扰项，比如多几条边，但核心思路不变。总之，记住最短路径就是所有路径里加起来最小的那个，别被图里的其他数字干扰了。