爱在冬季-澳洲留学签证费用

第十九讲 最短路线问题
在日常工作、生活和娱乐中，经常会遇到有关行程路线的 问题.在这
一讲里，我们主要解决的问题是如何确定从某处到另一处最短路线的条
数。
例1 下图4—1中的线段表示的是汽车所能经过的所有马路，这辆汽车从
A走到B处共有多少条最短路线？

分析 为了叙述方便，我们在各交叉点都标上字母.如图4—2.在这
里，首先 我们应该明确从A到B的最短路线到底有多长？从A点走到B
点，不论怎样走，最短也要走长方形AHB D的一个长与一个宽，即AD＋DB.
因此，在水平方向上，所有线段的长度和应等于AD；在竖直方向 上，所
有线段的长度和应等于DB.这样我们走的这条路线才是最短路线.为了保
证这一点，我 们就不应该走“回头路”，即在水平方向上不能向左走，在
竖直方向上不能向上走.因此只能向右和向下 走。
有些同学很快找出了从A到B的所有最短路线，即：
A→C→D→G→B A→C→F→G→B
A→C→F→I→B A→E→F→G→B
A→E→F→I→B A→E→H→I→B
通过验证，我们确信这六条路线都是从A到B的最短路 线.如果按照
上述方法找，它的缺点是不能保证找出所有的最短路线，即不能保证“不
漏”.当 然如果图形更复杂些，做到“不重”也是很困难的。
现在观察这种题是否有规律可循。
1.看C点：由A、由F和由D都可以到达C，而由F→C是由下向上走，
由D→C是由右向左走，这两 条路线不管以后怎样走都不可能是最短路线.
因此，从A到C只有一条路线。
同样道理：从A到D、从A到E、从A到H也都只有一条路线。
我们把数字“1”分别标在C、D、E、H这四个点上，如图4—2。
2.看F点：从上向下走是 C→F，从左向右走是E→F，那么从A点出
发到F，可以是A→C→F，也可以是A→E→F，共有两 种走法.我们在图4
—2中的F点标上数字“2”.2=1＋1.第一个“1”是从A→C的一种走法；
第二个“1”是从A→E的一种走法。
3.看G点：从上向下走是D→G，从左向右走是F→G，那么从A→G

我们在G点标上数 字“3”.3＝2+1，“2”是从A→F的两种走法，“1”
是从A→D的一种走法。
4.看I点：从上向下走是F→I，从左向右走是H→I，那么从出发点

在 I点标上“3”.3=2+1.“2”是从A→F的两种走法；“1”是从A→H
的一种走法。
5.看B点：从上向下走是G→B，从左向右走是I→B，那么从出发点
A→B可以这样走：

共有六种走法.6=3＋3，第一个“3”是从A→G共有三种走法，第二
个“3”是从A →I共有三种走法.在B点标上“6”。
我们观察图4—2发现每一个小格右下角上标的数正好是 这个小格右
上角与左下角的数的和，这个和就是从出发点A到这点的所有最短路线的
条数.这样 ，我们可以通过计算来确定从A→B的最短路线的条数，而且能
够保证“不重”也“不漏”。
解：由上面的分析可以得到如下的规律：每个格右上角与左下角所标
的数字和即为这格右下角应标的数字 .我们称这种方法为对角线法，也叫
标号法。

根据这种“对角线法”，B点标6，那么从A到B就有6条不同的最
短路线（见图4—3）。
答：从A到B共有6条不同的最短路线。
例2 图4—4是一个街道的平面图，纵横各有5条路， 某人从A到B处
（只能从北向南及从西向东），共有多少种不同的走法？


分析 因为B点在A点的东南方向，题目要求我们只能从北向南及从
西向东，也 就是要求我们走最短路线。解：如图4—5所示。
答：从A到B共有70种不同的走法。
例3 如图4—6，从甲地到乙地最近的道路有几条？

分析 要求从甲地到乙地最近的道路有几条，也就是求从甲地到乙地的最短路线有几条.把各交叉点标上字母，如图4—7.这道题的图形与例
1、例2的图形又有所区 别，因此，在解题时要格外注意是由哪两点的数
之和来确定另一点的。
①由甲→A有1种走法，由甲→F有1种走法，那么就可以确定从甲
→G共有1＋1＝2（种）走法。
②由甲→B有1种走法，由甲→D有1种走法，那么可以确定由甲→E
共有1+1＝2（种）走法.
③由甲→C有1种走法，由甲→H有2种走法，那么可以确定由甲→J
共有1+2=3（种）走法。
④由甲→G有2种走法，由甲→M有1种走法，那么可以确定从甲→N
共有2＋1=3（种）走法。
⑤从甲→K有2种走法，从甲→E有2种走法，那么从甲→L共有2
＋2=4（种）走法。
⑥从甲→N有3种走法，从甲→L有4种走法，那么可以确定从甲→P
共有3＋4=7（种）走法。
⑦从甲→J有3种走法，从甲→P有7种走法，那么从甲→乙共有
3+7=10（种）走法。
解：在图4—7中各交叉点标上数，乙处标上10，则从甲到乙共有10
条最近的道路。
例4 某城市的街道非常整齐，如图4—8所示，从西南角A处到东北角B
处要求走最近的路，并且不能通过十 字路口C（因正在修路）.问共有多
少种不同的走法？
分析 因为B点在A点的东北角，所以只能向东和向北走.为了叙述方
便，在各交叉点标上字母，如图4—9.


⑴从A→A
1
有1种 走法，A→A
11
有1种走法，那么可以确定从A→A
10
共有
1＋ 1=2（种）走法。
⑵从A→A
2
有1种走法，A→A
10
有2种 走法，那么可以确定从A→A
9
共有
1+2=3（种）走法。
⑶从A→A
3
有1种走法，A→A
9
有3种走法，那么可以确定从A→A
8共有
1+3=4（种）走法.
⑷从A→A
4
有1种走法，A→A
8
有4种走法，那么可以确定A→A
7
，共有1+4=5
（种）走法。 < br>⑸从A→A
5
有1种走法，A→A
7
有5种走法，那么可以确定A→A
6
共有1＋
5＝6（种）走法。
⑹从A→C
1
有1种走法 ，A→A
10
有2种走法，那么可以确定从A→C
2
共有
1+2=3 （种）走法。

⑺从A→C
2
有3种走法，A→A
9
有3种走法，那么可以确定A→C
3
共有3+3=6
（种）走法。
⑻从A→ C
4
可以是A→C→C
4
，也可以是A→A
7
→C
4
，因为C处正在修路，
所以A→C→C
4
行不通，只能由A
7→C
4
，由于A→A
7
有5种走法，所以A
→C
4也有5种走法，从A→A
6
有6种走法，所以从A→C
5
共有5+6＝1 1
（种）走法。
⑼从A→B
6
有1种走法，A→C
2
有3 种走法，那么可以确定从A→B
7
共有1
＋3=4（种）走法。
⑽从A→B
7
有4种走法，A→C
3
有6种走法，那么可以确定从A→B
8共有4
＋6=10（种）走法。
⑾从A→B
9
可以是A→B
8
→B
9
，也可以是A→C→B
9
，因为C处正在修路，
所以 A→C→B
9
行不通，只能由B
8
→B
9
，由于A→B8
有10种走法，所以A
→B
9
。也有10种走法.从A→C
4
有5种走法，所以从A→B
10
共有10+5=15
（种）走法。
⑿ 从A→C
5
有11种走法，A→B
10
有15种走法，那么从A →B
11
共有15+11=26
（种）走法。
⒀ 从A→B
5有1种走法，A→B
7
有4种走法，那么可以确定从A→B
4
共有
1+4=5（种）走法。
⒁ 从A→B
4
有5种走法，A→B
8
有10种走法，那么可以确定从A→B
3
共有
5+10=15（种）走法.
⒂从A→B
3
有15种走法，A→B
9
有10种走法，那么可以确定从A→B
2
共有
15＋10=25（种）走法。
⒃从A→B
2
有2 5种走法，A→B
10
有15种走法，那么可以确定从A→B
1
共
有 25+15=40（种）走法。
⒄从A→B
1
有40种走法，A→B
11< br>有26种走法，那么可以确定从A→B共有
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（只能由北向南、由西
向东），则共有多少种不同 的走法？

5.如图4-15所示，从甲地到乙地，最近的道路有几条？
6.图4-16为某城市的街道示意图，C处正在挖下水道，不能通车，从A到B
处的最短路线共有多少 条？

7.如图4-17所示是一个街道的平面图，在不走回头路、不走重复路的条件< br>下，可以有多少种不同的走法？

8.图4-18是某城市的主要公路示意图，今 在C、D、E、F、G、H路口修建立
交桥，车辆不能通行，那么从A到B的最近路线共有几条？