三年级奥数详解答案第十九讲最短路线问题.pdf

第十九讲 最短路线问题在日常工作、生活和娱乐中，经常会遇到有关行程路线的问题 . 在这一讲里，我们主要解决的问题是如何确定从某处到另一处最短路线的条数例 1 下图 4— 1 中的线段表示的是汽车所能经过的所有马路， 这辆汽车从A走到 B处共有多少条最短路线？分析 为了叙述方便，我们在各交叉点都标上字母 . 如图 4— 2. 在这里，首先我们应该明确从 A 到 B 的最短路线到底有多长？从 A 点走到 B点， 不论怎样走， 最短也要走长方形 AHBD的一个长与一个宽， 即 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— 22. 看 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→ A1 有 1 种走法， A→ A11 有 1 种走法，那么可以确定从 A→ A10 共有1＋ 1=2（种）走法⑵从 A→ A2 有 1 种走法， A→ A10 有 2 种走法，那么可以确定从 A→ A9 共有1+2=3（种）走法⑶从 A→ A3 有 1 种走法， A→ A9 有 3 种走法，那么可以确定从 A→ A8共有1+3=4（种）走法 . ⑷从 A→ A4有 1 种走法， A→ A8 有 4 种走法， 那么可以确定 A→ A7， 共有 1+4=5（种）走法⑸从 A→ A5 有 1 种走法， A→ A7 有 5 种走法，那么可以确定 A→ A6 共有 1＋5＝ 6（种）走法⑹从 A→ C1 有 1 种走法， A→ A10 有 2 种走法，那么可以确定从 A→ C2 共有1+2=3（种）走法。

⑺从 A→ C2有 3 种走法， A→ A9 有 3 种走法， 那么可以确定 A→ C3共有 3+3=6（种）走法⑻从 A→ C4 可以是 A→ C→ C4，也可以是 A→ A7→ C4，因为 C处正在修路，所以 A→ C→ C4 行不通，只能由 A7→ C4，由于 A→ A7 有 5 种走法，所以 A→ C4也有 5 种走法，从 A→ A6有 6 种走法，所以从 A→ C5 共有 5+6＝ 11（种）走法⑼从 A→ B6 有 1 种走法， A→ C2 有 3 种走法，那么可以确定从 A→ B7 共有 1＋ 3=4（种）走法⑽从 A→ B7 有 4 种走法， A→ C3 有 6 种走法，那么可以确定从 A→ B8 共有 4＋ 6=10（种）走法⑾从 A→ B9 可以是 A→ B8→ B9，也可以是 A→ C→ B9，因为 C处正在修路，所以 A→ C→ B9 行不通， 只能由 B8→ B9， 由于 A→ B8 有 10 种走法， 所以 A→ B9 也有 10 种走法 . 从 A→ C4 有 5 种走法， 所以从 A→ B10 共有 10+5=15（种）走法⑿ 从 A→ C5 有 11 种走法， A→ B10有 15种走法， 那么从 A→ B11 共有 15+11=26（种）走法。

⒀ 从 A→ B5 有 1 种走法， A→ B7有 4 种走法，那么可以确定从 A→ B4 共有1+4=5（种）走法⒁ 从 A→ B4 有 5 种走法， A→ B8 有 10 种走法， 那么可以确定从 A→ B3 共有5+10=15（种）走法 . ⒂从 A→ B3 有 15 种走法， A→ B9 有 10 种走法， 那么可以确定从 A→ B2 共有15＋ 10=25（种）走法⒃从 A→ B2 有 25 种走法， A→ B10 有 15 种走法，那么可以确定从 A→ B1 共有 25+15=40（种）走法⒄从 A→ B1 有 40 种走法， A→ B11 有 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 所示是一个街道的平面图，在不走回头路、不走重复路的条件下，可以有多少种不同的走法？8. 图 4-18 是某城市的主要公路示意图，今在 C、 D、 E、 F、 G、 H路口修建立交桥，车辆不能通行，那么从 A 到 B 的最近路线共有几条？。