最短路径问题

最短路径问题第1页/共18页看图思考：为什么有的人会经常践踏草地呢？绿地里本没有路，走的人多了……禁止践踏爱护草坪两点之间，线段最短第2页/共18页将军饮马问题：

两点之间线段最短这个问题早在古罗马时代就有了，传说亚历山大城有一位精通数学和物理的学者，名叫海伦．一天，一位罗马将军专程去拜访他，向他请教一个百思不得其解的问题：

将军每天骑马从城堡A出发，到城堡B，途中马要到小溪边饮水一次。将军问怎样走路程最短？

这就是被称为"将军饮马"而广为流传的问题。第3页/共18页P两点之间线段最短.

根据：BA(一)两点在一条直线两侧例1.如图：古希腊一位将军骑马从城堡A到城堡B，途中马要到小溪边饮水一次。问将军怎样走路程最短？最短路线：将军饮马：A---P---B.第4页/共18页

例2.如图：一位将军骑马从城堡A到城堡B，途中马要到河边饮水一次，问：这位将军怎样走路程最短？AB河两点在一条直线同侧(二)一次轴对称：第5页/共18页例2变式：已知：P、Q是△ABC的边AB、

AC上的点，你能在BC上确定一点R，使△PQR的周长最短吗？两点在一条直线同侧(二)一次轴对称：第6页/共18页草地河边.驻地A例3.如图：一位将军骑马从驻地A出发，先牵马去草地

OM吃草，再牵马去河边ON喝水，最后回到驻地A，问：这位将军怎样走路程最短？OMN(三)二次轴对称：一点在两相交直线内部第7页/共18页例3变式：已知P是△ABC的边BC上的点，你能在AB、AC上分别确定一点Q和R，使△PQR的周长最短吗？(三)二次轴对称：一点在两相交直线内部第8页/共18页例4：如图，A为马厩，B为帐篷，将军某一天要从马厩牵出马，先到草地边某一处牧马，再到河边饮马，然后回到帐篷，请你帮助确定这一天的最短路线。（四）二次轴对称：两点在两相交直线内部第9页/共18页ABA/B/PQ最短路线：APQBlMN第10页/共18页两点在一条河两侧例5.如图：古希腊一位将军骑马从城堡A到城堡B，A和B两地在一条河的两岸，现要在河上造一座桥MN.桥建在何处才能使将军从A到B的路径AMNB最短？（假定河的两岸是平行的直线，桥要与河垂直）BA(五)造桥选址问题第11页/共18页思维分析BA

1、如图假定任选位置造桥ＭＮ，连接ＡＭ和ＢＮ，从A到B的路径是AM+MN+BN，那么怎样确定什么情况下最短呢？ＭＮ

2、利用线段公理解决问题我们遇到了什么障碍呢？第12页/共18页

我们能否在不改变AM+MN+BN的前提下把桥转化到一侧呢？什么图形变换能帮助我们呢？思维火花各抒己见1、把A平移到岸边.2、把B平移到岸边.3、把桥平移到和A相连.4、把桥平移到和B相连.古有愚公移山，今有学子搬桥，呵呵!第13页/共18页上述方法都能做到使AM+MN+BN不变呢？请检验.合作与交流1、2两种方法改变了.怎样调整呢？把A或B分别向下或上平移一个桥长那么怎样确定桥的位置呢?第14页/共18页问题解决BAA1MN如图，平移A到A1，使ＡA1等于河宽，连接A1Ｂ交河岸于Ｎ作桥ＭＮ，此时路径ＡＭ＋ＭＮ＋ＢＮ最短.理由；另任作桥Ｍ１Ｎ１，连接ＡＭ１，ＢＮ１，Ａ１Ｎ１.Ｎ１Ｍ１由平移性质可知，ＡＭ＝Ａ１Ｎ，ＡＡ１＝ＭＮ＝Ｍ１Ｎ１，ＡＭ１＝Ａ１Ｎ１.AM+MN+BN转化为ＡＡ１＋Ａ１Ｂ，而ＡＭ１＋Ｍ１Ｎ１＋ＢＮ１转化为ＡＡ１＋Ａ１Ｎ１＋ＢＮ１.在△Ａ１Ｎ１Ｂ中，由线段公理知A1N1+BN1＞A1B因此ＡＭ１＋Ｍ１Ｎ１＋ＢＮ１＞AM+MN+BN第15页/共18页（2）把A，B在直线同侧的问题转化为在直线的两侧，化折线为直线，

将军饮马的实质：（3）可利用“两点之间线段最短”加以解决。（1）求最短路线问题------

通过几何变换找对称图形。（4）“选桥选址问题”移动桥宽后还是可利用“两点之间线段