史上最短路径的12道经典例题

这是一套专门讲解最短路径的经典题集。 第一部分我们要搞清楚三个重点:最短路径的基本模型、计算路径长度的一般方法,还有这个问题的数学本质。说白了,就是要学会用数形结合和函数思想把弯弯绕的路径拉直。 最短路径问题可是图论里的明星算法,核心只有一句话:在图里找一条从起点到终点最短的路。常见的题型有确定起点的、确定终点的、起点终点都定了的,还有求图中所有点对之间的最短路径。这些都离不开两点之间线段最短、轴对称和平移这些基本原理。 把这些原理吃透后,只要记住对称和平移这两个关键词,就能秒杀80%的题目了。现在把这套题练熟,不管是三角形、菱形还是坐标轴、抛物线这些背景下的问题都能轻松应对。 接下来我们来看12个基本例题。将军饮马、造桥选址还有费马点这三道古题现在还是中考的压轴大杀器呢。 做这些题的时候一定要找对称点,把折线变成直线。现在出题人更狠了,直接让你把三折变成直线来考——说到底还是先对称再平移最后求和或求差。 下面的每道题都是来自中考真题或模拟题,做完你就能举一反三了。 第一个例题主要是教你怎么用轴对称和平移来转化问题。比如例二,题目说在直线l同侧有两个点A和B,问PA+PB最小时的点P在哪里?还有PA-PB最大时的点P在哪里? 解题步骤是先把点B关于l作个对称点C,然后连接AC交l于P——这就是PA+PB最小的情况;再延长AB交l于P——这就是PA-PB最大的情况。 再比如例三,P是∠AOB内的一个点,P1和P2是P关于OA和OB的对称点。P1P2这条线和OA、OB分别交于M和N。如果P1P2的长度是8厘米,那么三角形PMN的周长是多少呢?答案很简单:周长就等于P1P2的长度8厘米——对称点一连线,周长立刻就看出来了。 像例四这种等腰直角三角形的问题也很典型。在等腰Rt△ABC中,D是BC边的中点,E是AB边上的一个动点。要想让EC+ED最小,E应该放在哪里呢? 做法是作点C关于AB的对称点C',然后连接C'D和AB的交点就是E——这样EC+ED最小的问题就转化成了折线变直线的问题。 还有例五那种桥址选址的题也非常经典。村庄A和B在小河两岸且河岸平行。现在要建一座垂直于河岸的桥CD,怎么选才能让A到B的路程最近呢? 解题步骤分四步:①过A点作AP垂直河岸a,然后在AP上向下截取AA'等于河宽;②连接A'B和河岸b交于D点;③过D作DE平行AA'交河岸a于C点;④最后连接AC——这样CD就是桥的最佳位置了。 这12道经典例题全部都是基于中考真题或模拟题改编的,把它们都吃透了之后你会发现做最短路径问题简直是小菜一碟。