11最短路线问题

公务员考试行测冲刺阶段提分技巧：1+1解决“最短路径问题”2004年，世界著名科学杂志《物理世界》举行了一场别开生面的评选活动，邀请世界各地的读者评选出自己心目中最伟大、最喜爱的公式、定理或定律。

最终的结果出乎很多人的意料，连幼儿园的小孩都知道的公式“1+1=2”不仅入选，而且还高居第一。

无独有偶，尼加拉瓜这个国家在鼎盛时期发行了一套纪念邮票《改变世界面貌的十个数学公式》，排在第一位仍然是“1+1=2”这个公式。

下面中公教育专家带大家来看看这个公式是如何解决公务员考试行测中“最短路径问题”的。

“最短路径问题”是公务员考试数学运算经常涉及的一种题型。

所谓最短路径问题是指在行程路线中，如何确定从某处到另一处最短路线的条数。

比如：【例】下图是一个街道的平面图，纵横各有7条路，某人从最左上处的点到最右下处，共有多少条最短路线?注：第一行街道交叉点分别用A1、A2、A3表示，第二行街道交叉点分别用B1、B2、B3表示，第三行街道分别用C1、C2、C3表示。

如果从最左上角(A1)到最右下角(C3)所走路径最短，则该人只能往右走或往下走，不能走回头路。

因为如果走回头路，所走路线肯定不是最短。

按照只能往右走或往下走，最短路线有：A1-A2-A3-B3-C3、A1-A2-B2-B3-C3、A1-A2-B2-C2-C3、A1-B1-B2-B3-C3、A1-B1-B2-C2-C3、A1-B1-C1-C2-C3。

这道题比较简单，可以一一列举，但是当街道数比较多的时候，一一列举就太麻烦了，中公教育专家带领大家从另外一个思路来求解。

要想到达C3，必须先到B3或者C2，到B3之后直接往下走即可，到C2之后直接往右走即可，所以到达C3的最短路径条数就应该等于到达B3最短路径条数加到达C2最短路径条数。

同理，想到达B3必须先到A3或者B2，所以到达B3最短路径条数等于到A3最短路径条数加到B2最短路径条数。

依次递推，得到下图：注：每点所标数字为从A1点到达该点最短路径条数。

最短路径问题(经典)精编版
最短路径问题是图论研究中的经典算法问题之一，其目的是在图中寻找两个节点之间的最短路径。

该问题可以分为以下几种情况：已知起始节点，求最短路径；已知终止节点，求最短路径；已知起始和终止节点，求两个节点之间的最短路径；求图中所有节点之间的最短路径。

这些问题的原型包括将军饮马、造桥选址和费马点。

解决最短路径问题需要涉及到许多数学知识，包括线段最短距离、垂线段最短距离、三角形三边关系、轴对称和平移等。

这些知识可以在角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴和抛物线等几何形状中得到应用。

解决最短路径问题的思路是找到对称点，实现折转直的过程。

近年来，出现了一些变式问题，例如三折线转直等，需要考生掌握解决方法。

最短路径问题有许多基本问题，其中包括确定起始节点和终止节点的最短路径问题，求图中所有节点之间的最短路径问
题等等。

在解决这些问题时，需要运用前述的数学知识和解决思路。

如果你对最短路径问题感兴趣，可以加入全国初中数学资料群，群号为xxxxxxxx0.。

中考数学专题复习学案六求最短路径问题【专题思路剖析】知识点：“两点之间线段最短”，“垂线段最短”，“点关于线对称”，“线段的平移”。

“饮马问题”，“造桥选址问题”。

考的较多的还是“饮马问题”，出题背景变式有角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等。

这类问题在中考中出现的频率很高，一般与垂线段最短、两点之间线段最短关系密切解题总思路：找点关于线的对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查。

在解决最短路径问题时，我们通常利用轴对称、平移等变换把不在一条直线上的两条线段转化到一条直线上，从而作出最短路径的方法来解决问题．【典型例题赏析】类型1 利用“垂线段最短”求最短路径问题例题1：（2015•辽宁省盘锦,第15题3分）如图，菱形ABCD的边长为2，∠DAB=60°，E为BC的中点，在对角线AC上存在一点P，使△PBE的周长最小，则△PBE的周长的最小值为．考点：轴对称-最短路线问题；菱形的性质．分析：连接BD，与AC的交点即为使△PBE的周长最小的点P；由菱形的性质得出∠BPC=90°，由直角三角形斜边上的中线性质得出PE=BE，证明△PBE是等边三角形，得出PB=BE=PE=1，即可得出结果．解答：解：连接BD，与AC的交点即为使△PBE的周长最小的点P；如图所示：∵四边形ABCD是菱形，∴AC⊥BD，AB=BC=CD=DA=2，∴∠BPC=90°，∵E为BC的中点，∴BE=BC=1，PE=BC=1，∴PE=BE，∵∠DAB=60°，∴∠ABC=120°，∴∠PBE=60°，∴△PBE是等边三角形，∴PB=BE=PE=1，∴PB+BE+PE=3；故答案为：3．点评：本题考查了菱形的性质、轴对称以及最短路线问题、直角三角形斜边上的中线性质；熟练掌握菱形的性质，并能进行推理计算是解决问题的关键．【方法点评】本题易错误的利用两点之间线段最短解决，解答时需要准确识图，找到图形对应的知识点．【变式练习】（2015•福建第16题 4分）如图，在△ABC中，∠ACB=90°，AB=5，BC=3，P是AB边上的动点（不与点B重合），将△BCP沿CP所在的直线翻折，得到△B′CP，连接B′A，则B′A 长度的最小值是．考点：翻折变换（折叠问题）．.分析：首先由勾股定理求得AC的长度，由轴对称的性质可知BC=CB′=3，当B′A有最小值时，即AB′+CB′有最小值，由两点之间线段最短可知当A、B′、C三点在一条直线上时，AB′有最小值．解答：解：在Rt△ABC中，由勾股定理可知：AC===4，由轴对称的性质可知：BC=CB′=3，∵CB′长度固定不变，∴当AB′+CB′有最小值时，AB′的长度有最小值．根据两点之间线段最短可知：A、B′、C三点在一条直线上时，AB′有最小值，∴AB′=AC﹣B′C=4﹣3=1．故答案为：1．点评：本题主要考查的是轴对称的性质、勾股定理和线段的性质，将求B′A的最小值转化为求AB′+CB′的最小值是解题的关键．类型2 利用“两点之间线段最短”求最短路径问题例题2：（2015•四川凉山州第26题5分）菱形ABCD在平面直角坐标系中的位置如图所示，顶点B（2，0），∠DOB=60°，点P是对角线OC上一个动点，E（0，﹣1），当EP+BP最短时，点P的坐标为．考点：菱形的性质；坐标与图形性质；轴对称-最短路线问题．.分析：点B的对称点是点D，连接ED，交OC于点P，再得出ED即为EP+BP最短，解答即可．解答：解：连接ED，如图，∵点B的对称点是点D，∴DP=BP，∴ED即为EP+BP最短，∵四边形ABCD是菱形，顶点B（2，0），∠DOB=60°，∴点D的坐标为（1，），∴点C的坐标为（3，），∴可得直线OC的解析式为：y=x，∵点E的坐标为（﹣1，0），∴可得直线ED的解析式为：y=（1+）x﹣1，∵点P是直线OC和直线ED的交点，∴点P的坐标为方程组的解，解方程组得：，所以点P的坐标为（），故答案为：（）．点评：此题考查菱形的性质，关键是根据一次函数与方程组的关系，得出两直线的解析式，求出其交点坐标．【方法点评】“两点(直线同侧)一线型”在直线上求一点到两点的和最短时，利用轴对称的知识作一点关于直线的对称点，连接对称点与另一点与直线的交点就是所求的点；“一点两线型”求三角形周长最短问题，作点关于两直线的对称点，连接两个对称点与两直线分别有两个交点，顺次连接所给的点与两交点即可得三角形；“两点两线型”求四边形的周长最短类比“一点两线型”即可．【变式练习】（2015•营口，第10题3分）如图，点P是∠AOB内任意一点，OP=5cm，点M和点N分别是射线OA和射线OB上的动点，△PMN周长的最小值是5cm，则∠AOB的度数是（）A．25° B．30° C．35° D．40°考点：轴对称-最短路线问题．分析：分别作点P关于OA、OB的对称点C、D，连接CD，分别交OA、OB于点M、N，连接OC、OD、PM、PN、MN，由对称的性质得出PM=CM，OP=OC，∠COA=∠POA；PN=DN，OP=OD，∠DOB=∠POB，得出∠AOB=∠COD，证出△OCD是等边三角形，得出∠COD=60°，即可得出结果．解答：解：分别作点P关于OA、OB的对称点C、D，连接CD，分别交OA、OB于点M、N，连接OC、OD、PM、PN、MN，如图所示：∵点P关于OA的对称点为C，关于OB的对称点为D，∴PM=CM，OP=OC，∠COA=∠POA；∵点P关于OB的对称点为D，∴PN=DN，OP=OD，∠DOB=∠POB，∴OC=OP=OD，∠AOB=∠COD，∵△PMN周长的最小值是5cm，∴PM+PN+MN=5，∴CM+DN+MN=5，即CD=5=OP，∴OC=OD=CD，即△OCD是等边三角形，∴∠COD=60°，∴∠AOB=30°；故选：B．点评：本题考查了轴对称的性质、最短路线问题、等边三角形的判定与性质；熟练掌握轴对称的性质，证明三角形是等边三角形是解决问题的关键．类型3、求圆上点，使这点与圆外点的距离最小的方案设计在此问题中可根据圆上最远点与最近点和点的关系可得最优设计方案。

在日常生活、工作中，经常会遇到有关行程路线的问题。

比如：邮递员送信，要穿遍所有的街道，为了少走冤枉路，需要选择一条最短的路线；旅行者希望寻求最佳旅行路线，以求能够走最近的路而达到目的地，等等。

这样的问题，就是我们所要研究学习的“最短路线问题”。

典型例题例[1] 假如直线AB 是一条公路，公路两旁有甲乙两个村子，如下图1。

现在要在公路上修建一个公共汽车站，让这两个村子的人到汽车站的路线之和最短。

问：车站应该建在什么地方？分析 如果只考虑甲村的人距离公路AB 最近，只要由甲村向公路AB 画一条垂直线，交AB 于C 点，那么C 点是甲村到公路AB 最甲乙 AB 甲乙图1图2最短路线近的点，但是乙村到C点就较远了。

反过来，由乙村向公路AB画垂线，交AB于D点，那么D点是乙村到公路AB最近的点。

但是这时甲村到公路AB的D点又远了。

因为本题要求我们在公路AB上取的建站点，能够兼顾甲村和乙村的人到这个车站来不走冤枉路（既路程之和最短），根据我们的经验：两个地点之间走直线最近，所以，只要在甲村乙村间连一条直线，这条直线与公路AB交点P，就是所求的公共汽车站的建站点了（图2）。

解用直线把甲村、乙村连起来。

因为甲村乙村在公路的两侧，所以这条连线必与公路AB有一个交点，设这个交点为P，那么在P 点建立汽车站，就能使甲村乙村的人到汽车站所走的路程之和最短。

例[2] 一个邮递员投送信件的街道如图3所示，图上数字表示各段街道的千米数。

他从邮局出发，要走遍各街道，最后回到邮局。

问：走什么样的路线最合理？全程要走多少千米？3分析选择最短的路线最合理。

那么，什么路线最短呢？一笔画路线应该是最短的。

邮递员从邮局出发，还要回到邮局，按一笔画问题，就是从偶点出发，回到偶点。

因此，要能一笔把路线画出来，必须途径的各点全是偶点。

但是图中有8个奇点，显然邮递员要走遍所有街道而又不走重复的路是不可能的。

要使邮递员从邮局出发，仍回到邮局，必须使8个奇点都变成偶点，就是要考虑应在哪些街道上重复走，也就是相当于在图上添哪些线段，能使奇点变成偶点。

最短路径问题
【问题概述】最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径
组成的)中两结点之间的最短路径.算法具体的形式包括
①确定起点的最短路径问题-即已知起始结点,求最短路径的问题
②确定终点的最短路径问题-与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题
③确定起点终点的最短路径问题-即已知起点和终点,求两结点之间的最短路径
④全局最短路径问题-求图中所有的最短路径
【问题原型】“将军饮马”,“造桥选址”,“费马点”
【涉及知识】“两点之间线段最短”,“垂线段最短”,“三角形三边关系”,“轴对称
【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等【解题思路】找对称点实现“折”转“直”,近两年出现"三折线”转“直”等变式问题考
【十二个基本问题】。