1、第4讲最短路线问题第四讲 最短路线问题在日常工作、生活和娱乐中，经常会遇到有关行程路线的问题.在这一讲里，我们主要解决的问题是如何确定从某处到另一处最短路线的条数。例1 下图41中的线段表示的是汽车所能经过的所有马路，这辆汽车从A走到B处共有多少条最短路线？分析 为了叙述方便，我们在各交叉点都标上字母.如图42.在这里，首先我们应该明确从A到B的最短路线到底有多长？从A点走到B点，不论怎样走，最短也要走长方形AHBD的一个长与一个宽，即ADDB.因此，在水平方向上，所有线段的长度和应等于AD；在竖直方向上，所有线段的长度和应等于DB.这样我们走的这条路线才是最短路线.为了保证这一点，我们就不应
2、该走“回头路”，即在水平方向上不能向左走，在竖直方向上不能向上走.因此只能向右和向下走。有些同学很快找出了从A到B的所有最短路线，即：ACDGB ACFGBACFIB AEFGBAEFIB AEHIB通过验证，我们确信这六条路线都是从A到B的最短路线.如果按照上述方法找，它的缺点是不能保证找出所有的最短路线，即不能保证“不漏”.当然如果图形更复杂些，做到“不重”也是很困难的。现在观察这种题是否有规律可循。1.看C点：由A、由F和由D都可以到达C，而由FC是由下向上走，由DC是由右向左走，这两条路线不管以后怎样走都不可能是最短路线.因此，从A到C只有一条路线。同样道理：从A到D、从A到E、从A到
3、H也都只有一条路线。我们把数字“1”分别标在C、D、E、H这四个点上，如图42。2.看F点：从上向下走是CF，从左向右走是EF，那么从A点出发到F，可以是ACF，也可以是AEF，共有两种走法.我们在图42中的F点标上数字“2”.2=11.第一个“1”是从AC的一种走法；第二个“1”是从AE的一种走法。3.看G点：从上向下走是DG，从左向右走是FG，那么从AG我们在G点标上数字“3”.32+1，“2”是从AF的两种走法，“1”是从AD的一种走法。4.看I点：从上向下走是FI，从左向右走是HI，那么从出发点在I点标上“3”.3=2+1.“2”是从AF的两种走法；“1”是从AH的一种走法。5.看B点
4、：从上向下走是GB，从左向右走是IB，那么从出发点AB可以这样走：共有六种走法.6=33，第一个“3”是从AG共有三种走法，第二个“3”是从AI共有三种走法.在B点标上“6”。我们观察图42发现每一个小格右下角上标的数正好是这个小格右上角与左下角的数的和，这个和就是从出发点A到这点的所有最短路线的条数.这样，我们可以通过计算来确定从AB的最短路线的条数，而且能够保证“不重”也“不漏”。解：由上面的分析可以得到如下的规律：每个格右上角与左下角所标的数字和即为这格右下角应标的数字.我们称这种方法为对角线法，也叫标号法。根据这种“对角线法”，B点标6，那么从A到B就有6条不同的最短路线（见图43）。
5、答：从A到B共有6条不同的最短路线。例2 图44是一个街道的平面图，纵横各有5条路， 某人从A到B处（只能从北向南及从西向东），共有多少种不同的走法？分析因为B点在A点的东南方向，题目要求我们只能从北向南及从西向东，也就是要求我们走最短路线。解：如图45所示。答：从A到B共有70种不同的走法。例3 如图46，从甲地到乙地最近的道路有几条？分析 要求从甲地到乙地最近的道路有几条，也就是求从甲地到乙地的最短路线有几条.把各交叉点标上字母，如图47.这道题的图形与例1、例2的图形又有所区别，因此，在解题时要格外注意是由哪两点的数之和来确定另一点的。由甲A有1种走法，由甲F有1种走法，那么就可以确定从
6、甲G共有112（种）走法。由甲B有1种走法，由甲D有1种走法，那么可以确定由甲E共有1+12（种）走法.由甲C有1种走法，由甲H有2种走法，那么可以确定由甲J共有1+2=3（种）走法。由甲G有2种走法，由甲M有1种走法，那么可以确定从甲N共有21=3（种）走法。从甲K有2种走法，从甲E有2种走法，那么从甲L共有22=4（种）走法。从甲N有3种走法，从甲L有4种走法，那么可以确定从甲P共有34=7（种）走法。从甲J有3种走法，从甲P有7种走法，那么从甲乙共有3+7=10（种）走法。解：在图47中各交叉点标上数，乙处标上10，则从甲到乙共有10条最近的道路。例4 某城市的街道非常整齐，如图48所示
7、，从西南角A处到东北角B处要求走最近的路，并且不能通过十字路口C（因正在修路）.问共有多少种不同的走法？分析 因为B点在A点的东北角，所以只能向东和向北走.为了叙述方便，在各交叉点标上字母，如图49. 从AA1有1种走法，AA11有1种走法，那么可以确定从AA10共有11=2（种）走法。 从AA2有1种走法，AA10有2种走法，那么可以确定从AA9共有1+2=3（种）走法。 从AA3有1种走法，AA9有3种走法，那么可以确定从AA8共有1+3=4（种）走法.从AA4有1种走法，AA8有4种走法，那么可以确定AA7，共有1+4=5（种）走法。 从AA5有1种走法，AA7有5种走法，那么可以确定A
8、A6共有156（种）走法。 从AC1有1种走法，AA10有2种走法，那么可以确定从AC2共有1+2=3（种）走法。 从AC2有3种走法，AA9有3种走法，那么可以确定AC3共有3+3=6（种）走法。 从AC4可以是ACC4，也可以是AA7C4，因为C处正在修路，所以ACC4行不通，只能由A7C4，由于AA7有5种走法，所以AC4也有5种走法，从AA6有6种走法，所以从AC5共有5+611（种）走法。从AB6有1种走法，AC2有3种走法，那么可以确定从AB7共有13=4（种）走法。从AB7有4种走法，AC3有6种走法，那么可以确定从AB8共有46=10（种）走法。从AB9可以是AB8B9，也可以
9、是ACB9，因为C处正在修路，所以ACB9行不通，只能由B8B9，由于AB8有10种走法，所以AB9。也有10种走法.从AC4有5种走法，所以从AB10共有10+5=15（种）走法。 从AC5有11种走法，AB10有15种走法，那么从AB11共有15+11=26（种）走法。 从AB5有1种走法，AB7有4种走法，那么可以确定从AB4共有1+4=5（种）走法。 从AB4有5种走法，AB8有10种走法，那么可以确定从AB3共有5+10=15（种）走法.(15)从AB3有15种走法，AB9有10种走法，那么可以确定从AB2共有1510=25（种）走法。(16)从AB2有25种走法，AB10有15种走
10、法，那么可以确定从AB1共有25+15=40（种）走法。(17)从AB1有40种走法，AB11有26种走法，那么可以确定从AB共有40+26=66（种）走法。解：如图4-10所示。答：从A到B共有66种不同的走法.习题四1.如果沿图4-11中的线段，以最短的路程，从A点出发到B点，共有多少种不同的走法？2.从学校到少年宫有4条东西向的马路和3条南北向的马路相通.如图4-12，李楠从学校出发，步行到少年宫（只许向东和向南行进），最多有多少种不同的行走路线？3.如图 4-13，从P到Q共有多少种不同的最短路线？4.如图4-14所示为某城市的街道图，若从A走到B（只能由北向南、由西向东），则共有多少
11、种不同的走法？5.如图4-15所示，从甲地到乙地，最近的道路有几条？6.图4-16为某城市的街道示意图，C处正在挖下水道，不能通车，从A到B处的最短路线共有多少条？7.如图4-17所示是一个街道的平面图，在不走回头路、不走重复路的条件下，可以有多少种不同的走法？8.图4-18是某城市的主要公路示意图，今在C、D、E、F、G、H路口修建立交桥，车辆不能通行，那么从A到B的最近路线共有几条？习题四解答1.解：答：从A到B共有126种走法。2.解：答：从学校到少年宫最多有10种不同的行走路线。3.解：答：从P到Q共有126条不同的最短路线.4.解：答：从A到B共有12种走法。5.解：答：从甲到乙最近的道路有11条。6.解：答：从A到B的最短路线有431条.7.解：答：从A到B有25种不同的走法。8.解：答：从A到B最短的路线有699条.
