在日常工作、生活和娛樂中，經(jīng)常會遇到有關(guān)行程路線的問題.在這一講里，我們主要解決的問題是如何確定從某處到另一處最短路線的條數(shù)。

    例1 下圖4—1中的線段表示的是汽車所能經(jīng)過的所有馬路，這輛汽車從A走到B處共有多少條最短路線？

　　分析 為了敘述方便，我們在各交叉點(diǎn)都標(biāo)上字母.如圖4—2.在這里，首先我們應(yīng)該明確從A到B的最短路線到底有多長？從A點(diǎn)走到B點(diǎn)，不論怎樣走，最短也要走長方形AHBD的一個長與一個寬，即AD＋DB.因此，在水平方向上，所有線段的長度和應(yīng)等于AD；在豎直方向上，所有線段的長度和應(yīng)等于DB.這樣我們走的這條路線才是最短路線.為了保證這一點(diǎn)，我們就不應(yīng)該走“回頭路”，即在水平方向上不能向左走，在豎直方向上不能向上走.因此只能向右和向下走。

　　有些同學(xué)很快找出了從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

　　通過驗(yàn)證，我們確信這六條路線都是從A到B的最短路線.如果按照上述方法找，它的缺點(diǎn)是不能保證找出所有的最短路線，即不能保證“不漏”.當(dāng)然如果圖形更復(fù)雜些，做到“不重”也是很困難的。

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

　　1.看C點(diǎn)：由A、由F和由D都可以到達(dá)C，而由F→C是由下向上走，由D→C是由右向左走，這兩條路線不管以后怎樣走都不可能是最短路線.因此，從A到C只有一條路線。

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

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

　　2.看F點(diǎn)：從上向下走是C→F，從左向右走是E→F，那么從A點(diǎn)出發(fā)到F，可以是A→C→F，也可以是A→E→F，共有兩種走法.我們在圖4—2中的F點(diǎn)標(biāo)上數(shù)字“2”.2=1＋1.第一個“1”是從A→C的一種走法；第二個“1”是從A→E的一種走法。

　　3.看G點(diǎn)：從上向下走是D→G，從左向右走是F→G，那么從A→G

　　

　　我們在G點(diǎn)標(biāo)上數(shù)字“3”.3＝2+1，“2”是從A→F的兩種走法，“1”是從A→D的一種走法。

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

　　

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

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

　　

　　共有六種走法.6=3＋3，第一個“3”是從A→G共有三種走法，第二個“3”是從A→I共有三種走法.在B點(diǎn)標(biāo)上“6”。

　　我們觀察圖4—2發(fā)現(xiàn)每一個小格右下角上標(biāo)的數(shù)正好是這個小格右上角與左下角的數(shù)的和，這個和就是從出發(fā)點(diǎn)A到這點(diǎn)的所有最短路線的條數(shù).這樣，我們可以通過計(jì)算來確定從A→B的最短路線的條數(shù)，而且能夠保證“不重”也“不漏”。

　　解：由上面的分析可以得到如下的規(guī)律：每個格右上角與左下角所標(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條不同的最短路線。