最短路径问题

《最短路径问题》由会员分享，可在线阅读，更多相关《最短路径问题（10页珍藏版）》请在金锄头文库上搜索。

1、13.4课题学习课题学习 最短路径问题最短路径问题如图所示：从如图所示：从A A地到地到B B地有三条路可供地有三条路可供选择，你会选择哪条路距离最短？你选择，你会选择哪条路距离最短？你的理由是什么？的理由是什么？两点之间线段最短两点之间线段最短问题问题1相传，古希腊亚历山大里亚城里有一位久相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦有一天，一位将军专程拜访负盛名的学者，名叫海伦有一天，一位将军专程拜访海伦，求教一个百思不得其解的问题：海伦，求教一个百思不得其解的问题：从图中的从图中的A 地出发，到一条笔直的河边地出发，到一条笔直的河边l 饮马，然饮马，然后到后到B 地到河边什么

2、地方饮马可使他所走的路线全程地到河边什么地方饮马可使他所走的路线全程最短？最短？探索新知探索新知BAl问题二：如图，要在燃气管道问题二：如图，要在燃气管道L L上修建一个泵上修建一个泵站，分别向站，分别向A A、B B两镇供气，泵站修在管道两镇供气，泵站修在管道的什么地方，可使所用的输气管线最短？的什么地方，可使所用的输气管线最短？P所以泵站建在点所以泵站建在点P P可使输气管线最短可使输气管线最短如图，如果如图，如果A A，B B在燃气管道在燃气管道L L的同旁，的同旁，泵站应修在管道的什么地方，可使所泵站应修在管道的什么地方，可使所用的输气管线最短？用的输气管线最短？ABC总结经验：总结经

3、验： 实际上是通过轴对称变换，把实际上是通过轴对称变换，把A，B在直线同侧的问题转化为在直线在直线同侧的问题转化为在直线的两侧，从而可利用的两侧，从而可利用“两点之间线段两点之间线段最短最短”加以解决。加以解决。如果另一侧放着一些小木棍，小明先去捡球，如果另一侧放着一些小木棍，小明先去捡球，还要跑到另一侧去取木棍，则小明又应按还要跑到另一侧去取木棍，则小明又应按怎样的路线跑，去捡哪个位置的球，小木怎样的路线跑，去捡哪个位置的球，小木棍，才能最快跑到目的地棍，才能最快跑到目的地A处。处。DEC路线：小明路线：小明DEA如果我们把台球桌做成等边三角形的形状，如果我们把台球桌做成等边三角形的形状，那

4、么从那么从AC中点中点D处发出的球，能否依次经处发出的球，能否依次经BC、AB两条边反射回到两条边反射回到D处？如果你认为处？如果你认为不能，请说明理由；如果你认为能，请作不能，请说明理由；如果你认为能，请作出球运动的路线。出球运动的路线。ABCD如图，小河边有两个村庄A，B，要在河边建一自来水厂向A村与B村供水(1)若要使厂部到A，B村的距离相等，则应选择在哪建厂？(2)若要使厂部到A，B两村的水管最短，应建在什么地方？分析：分析：(1)到A，B两点距离相等，可联想到“线段垂直平分线上的点到线段两端点的距离相等”，又要在河边，所以作AB的垂直平分线，与EF的交点即为符合条件的点(2)要使厂部

5、到A村、B村的距离之和最短，可联想到“两点之间线段最短”，作A(或B)点关于EF的对称点，连接对称点与B点，与EF的交点即为所求解：解：(1)如图1，取线段AB的中点G，过中点G画AB的垂线，交EF于P，则P到A，B的距离相等也可分别以A、B为圆心，以大于AB为半径画弧，两弧交于两点，过这两点作直线，与EF的交点P即为所求(2)如图2，画出点A关于河岸EF的对称点A，连接AB交EF于P，则P到A，B的距离和最短如图，从A地到B地经过一条小河(河岸平行)，今欲在河上建一座与两岸垂直的桥，应如何选择桥的位置才能使从A地到B地的路程最短？思路导引：从A到B要走的路线是AMNB，如图所示，而MN是定值

6、，于是要使路程最短，只要AMBN最短即可此时两线段应在同一平行方向上，平移MN到AC，从C到B应是余下的路程，连接BC的线段即为最短的，此时不难说明点N即为建桥位置，MN即为所建的桥解：解：(1)如图2，过点A作AC垂直于河岸，且使AC等于河宽(2)连接BC与河岸的一边交于点N.(3)过点N作河岸的垂线交另一条河岸于点M.则MN为所建的桥的位置如图，如图，A为马厩，为马厩，B为帐篷，牧马人某一天要为帐篷，牧马人某一天要从马厩牵出马，先到草地边某一处牧马，从马厩牵出马，先到草地边某一处牧马，再到河边给马喝水，然后回到帐篷，请你再到河边给马喝水，然后回到帐篷，请你帮助他确定这一天的最短路线。帮助他确定这一天的最短路线。