小學(xué)三年級下冊數(shù)學(xué)奧數(shù)知識點(diǎn)講解第4課《最短路線問題》試題附答案

第四講最短路線問題

在日常工作、生活和娛樂中，經(jīng)常會遇到有關(guān)行程路線的問題.在這一講

里，我們主要解決的問題是如何確定從某處到另一處最短路線的條數(shù)。

例1下圖4—1中的線段表示的是汽車所能經(jīng)過的所有馬路，這輛汽車從送到B

處共有多少條最短路線？

1C1

E2F3

1

[H3I6

圖4-1圖4-2

例2圖4—4是一個(gè)街道的平面圖，縱橫各有5條路，某人從A到B處（只能從北

向南及從西向東），共有多少種不同的走法？

例3如圖4—6,從甲地到乙地最近的道路有幾條?

甲

圖4-6

例4某城市的街道非常整齊，如圖4—8所示，從西南角故b到東北角B處要求走

最近的路，并且不能通過十字路口，（因正在修路）.問共有多少種不同的走

法？

圖4-8

答案

第四講最短路線問題

在日常工作、生活和娛樂中，經(jīng)常會遇到有關(guān)行程路線的問題.在這一講

里，我們主要解決的問題是如何確定從某處到另一處最短路線的條數(shù)。

例1下圖4—1中的線段表示的是汽車所能經(jīng)過的所有馬路，這輛汽車從建到B

處共有多少條最短路線？

1C1

E2F3

1

1H3I6

圖4T圖4-2

分析為了敘述方便，我們在各交叉點(diǎn)都標(biāo)上字母.如圖4—2.在這里，首先

我們應(yīng)該明確從A到B的最短路線到底有多長？從A點(diǎn)走到B點(diǎn)，不論怎樣走，最

短也要走長方形AHBD的一個(gè)長與一個(gè)寬，即AD+DB.因此，在水平方向上，所有

線段的長度和應(yīng)等于AD；在豎直方向上，所有線段的長度和應(yīng)等于DB.這樣我們

走的這條路線才是最短路線.為了保證這一點(diǎn)，我們就不應(yīng)該走“回頭路”，即

在水平方向上不能向左走，在豎直方向上不能向上走.因此只能向右和向下走。

有些同學(xué)很快找出了從A到B的所有最短路線，即:

A-C-D-G-BA-C-F-G-B

A-C-F-*I-BA-E-F-G-B

A—EfF——BAT—I—B

通過驗(yàn)證，我們確信這六條路線都是從A到B的最短路線.如果按照上述方法

找，它的缺點(diǎn)是不能保證找出所有的最短路線，即不能保證“不漏”.當(dāng)然如果

圖形更復(fù)雜些，做到“不重”也是很困難的。

現(xiàn)在觀察這種題是否有規(guī)律可循。

1.看C點(diǎn)：由A、由F和由D都可以到達(dá)C,而由F—C是由下向上走，由D-＜是

由右向左走，這兩條路線不管以后怎樣走都不可能是最短路線.因此，從A到C只

有一條路線。

同樣道理：從A到D、從A到E、從A到H也都只有一條路線。

我們把數(shù)字“1”分別標(biāo)在C、D、E、H這四個(gè)點(diǎn)上，如圖4一2。

2.看F點(diǎn)：從上向下走是C—F,從左向右走是E-F,那么從A點(diǎn)出發(fā)到F,可

以是A-C-F,也可以是AfE—F,共有兩種走法.我們在圖4—2中的F點(diǎn)標(biāo)上數(shù)

字“2”.2=1+1.第一個(gè)“1”是從A-C的一種走法；第二個(gè)“1”是從A-E的一

種走法。

3.看G點(diǎn)：從上向下走是D-G,從左向右走是F-G,那么從AfG

可以這樣走：A-C-D-G,:二:XF-G,共有三種走法.

我們在G點(diǎn)標(biāo)上數(shù)字“33=2+1,“2”是從A-F的兩種走法，“1”是從

AfD的一種走法。

4.看I點(diǎn)：從上向下走是Ffl,從左向右走是H-I,那么從出發(fā)點(diǎn)

A—?C

Afi可以這樣走：口＞*尸-＞1,AfE-*HfI,共有三種走法，

在I點(diǎn)標(biāo)上“33=2+1.“2”是從A-F的兩種走法；“1”是從A-H的一種

走法。

5.看B點(diǎn)：從上向下走是G—B,從左向右走是I—B,那么從出發(fā)點(diǎn)A—B可以

這樣走：

A—"DA—E—F、

A—C-F^-*GfBAfEfFI-B

A—"FA—EfH

共有六種走法.6=3+3,第一個(gè)“3”是從A-G共有三種走法，第二個(gè)“3”

是從A->I共有三種走法.在B點(diǎn)標(biāo)上“6”。

我們觀察圖4—2發(fā)現(xiàn)每一個(gè)小格右下角上標(biāo)的數(shù)正好是這個(gè)小格右上角與

左下角的數(shù)的和，這個(gè)和就是從出發(fā)點(diǎn)A到這點(diǎn)的所有最短路線的條數(shù).這樣，

我們可以通過計(jì)算來確定從A-B的最短路線的條數(shù)，而且能夠保證“不重”也

解：由上面的分析可以得到如下的規(guī)律：每個(gè)格右上角與左下角所標(biāo)的數(shù)

字和即為這格右下角應(yīng)標(biāo)的數(shù)字.我們稱這種方法為對角線法，也叫標(biāo)號法。

根據(jù)這種“對角線法”，B點(diǎn)標(biāo)6,那么從A到B就有6條不同的最短路線（見

圖4—3）。

答：從A到B共有6條不同的最短路線。

例2圖4-4是一個(gè)街道的平面圖，縱橫各有5條路，某人從A到B處（只能從北

向南及從西向東），共有多少種不同的走法？

B

圖4-4

分析因?yàn)锽點(diǎn)在A點(diǎn)的東南方向，題目要求我們只能從北向南及從西向東,

也就是要求我們走最短路線。解：如圖4—5所示。

答：從A到B共有70種不同的走法。

例3如圖4—6,從甲地到乙地最近的道路有幾條？

￥

---------'乙

圖4-6

分析要求從甲地到乙地最近的道路有幾條，也就是求從甲地到乙地的最短

路線有幾條.把各交叉點(diǎn)標(biāo)上字母，如圖4—7.這道題的圖形與例1、例2的圖形

又有所區(qū)別，因此，在解題時(shí)要格外注意是由哪兩點(diǎn)的數(shù)之和來確定另一點(diǎn)

的。

①由甲fA有1種走法，由甲一F有1種走法，那么就可以確定從甲-G共有1

+1=2（種）走法。

②由甲fB有1種走法，由甲->D有1種走法，那么可以確定由甲fE共有1+1

=2（種）走法.

③由甲-C有1種走法，由甲有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（種）走法。

⑦從甲fj有3種走法，從甲-P有7種走法，那么從甲-乙共有3+7=10

（種）走法。

解：在圖4—7中各交叉點(diǎn)標(biāo)上數(shù)，乙處標(biāo)上10,則從甲到乙共有10條最近

的道路。

例4某城市的街道非常整齊，如圖4一8所示，從西南角樹到東北角B處要求走

最近的路，并且不能通過十字路口，（因正在修路）.問共有多少種不同的走

法？

分析因?yàn)锽點(diǎn)在A點(diǎn)的東北角，所以只能向東和向北走.為了敘述方便，在

各交叉點(diǎn)標(biāo)上字母，如圖4一9.

圖4-8

①從AfAi有1種走法，AfAi：有1種走法,那么可以確定從A—"A：:共有1+

1=2（種）走法。

②從AfA有1種走法，A—Ai：有2種走法,那么可以確定從A—A洪有1+2=3

（種）走法。

③從A—A:有1種走法，A—A布3種走法，那么可以確定從A—As共有1+3=4

（種）走法.

④從A—As有1種走法，A—出有4種走法，那么可以確定A—A：,共有1+4=5

（種）走法。

⑤從AfA:有1種走法，A—A;有5種走法，那么可以確定A-*AE共有1+5=6

（種）走法。

⑥從A—Ci有1種走法，A—Ai：有2種走法，那么可以確定從Af（k共有1+2=3

（種）走法。

⑦從AfQ有3種走法，A—A有3種走法，那么可以確定AfC共有3+3=6

（種）走法。

⑧從A-*Ca可以是A-*C-*口，也可以是Af因?yàn)镃處正在修路，所以

A—＜一＜：行不通，只能由A—由于AfA:有5種走法，所以A—C也有5種走

法，從AfA商6種走法，所以從A-＜洪有5+6=11（種）走法。

⑨從AfBe有1種走法，A-Q有3種走法，那么可以確定從A-B：共有1+3=4

（種）走法。

?從AfB：有4種走法，AfC:有6種走法，那么可以確定從A~B三共有4+6=10

（種）走法。

（II］從A—可以是AfBE—也可以是AfC—Bn因?yàn)镃處正在修路，所以A

fC-B行不通，只能由氏—Bm,由于A~*BE有10種走法，所以A—B”也有10種走

法.從AT：清5種走法，所以從A—B：:夾有10+5=15（祎）定法。

02］從AfC:有11種走法，AfBi：有15種走法，那么從AfB□共有15+11=26

（種）走法。

03］從A~BE有1種走法，AfB：有4種走法，那么可以確定從A-B,共有1+4=5

（種）走法。

（14）從AfB」有5種走怯，A-BE有10種走法，那么可以確定從A-B3共有

5+10=15（種）走法.

（15）從人-*8:有15種走法，A~*B有10種走法，那么可以確定從A—Bz共有15

+10=25（種）走法。

（16）從A-Bz有25種走法，A-Bi：有15種走法，那么可以確定從AfB1共有

25+15=40（種）走法。

（17）從A—B：有40種走法，A—Bu有26種走法，那么可以確定從AfB共有

40+26=66（種）走法。

解：如圖4-10所示。

答：從A到B共有66種不同的走法.

習(xí)題四

1.如果沿圖4-11中的線段，以最短的路程，從A點(diǎn)出發(fā)到B點(diǎn)，共有多少種

不同的走法？

A

圖4-11B

2.從學(xué)校到少年宮有4條東西向的馬路和3條南北向的馬路相通.如圖4-12,

李楠從學(xué)校出發(fā)，步行到少年宮（只許向東和向南行進(jìn)），最多有多少種不同

的行走路線？

3.如圖4-13,從P到Q共有多少種不同的最短路線?

4.如圖4-14所示為某城市的街道圖,若從A走到B（只能由北向南、由西向

東），則共有多少種不同的走法？

1H

圖4-1304-14

5.如圖4-15所示，從甲地到乙地，最近的道路有幾條？

6.圖4-16為某城市的街