Dijkstra算法計(jì)算最短路的教學(xué)探析

丁學(xué)利

(阜陽(yáng)職業(yè)技術(shù)學(xué)院，安徽 阜陽(yáng) 236031)

圖論是離散數(shù)學(xué)中實(shí)踐和理論融合較強(qiáng)的一部分內(nèi)容,尤其是最短路的計(jì)算問(wèn)題,其實(shí)際應(yīng)用范圍較為廣泛。在現(xiàn)實(shí)生活中的許多問(wèn)題,如交通網(wǎng)中的最短路問(wèn)題,物流中的優(yōu)化問(wèn)題,計(jì)算機(jī)學(xué)科相關(guān)問(wèn)題的研究,都涉及到圖論中的最短路的計(jì)算。計(jì)算最短路的算法最常用的是Dijkstra算法,此外還有Floyd算法等。Dijkstra算法是最早研究最短路的有效算法之一,它是計(jì)算從帶權(quán)圖中的某一固定結(jié)點(diǎn)(源點(diǎn))到其余結(jié)點(diǎn)的最短路徑,但要求權(quán)值不能為負(fù)。許多圖論教材對(duì)Dijkstra算法都進(jìn)行了介紹,但有些講解較簡(jiǎn)潔,學(xué)生不易理解,再加高職數(shù)學(xué)基礎(chǔ)較薄弱,因此學(xué)生在實(shí)際計(jì)算的時(shí)候卻經(jīng)常出現(xiàn)錯(cuò)誤。對(duì)此,本文通過(guò)對(duì)Dijkstra算法從不同視角進(jìn)行直觀、有效的講解,將有助于學(xué)生發(fā)散思維的培養(yǎng)和鍛煉,同時(shí)對(duì)學(xué)生的學(xué)習(xí)興趣和教學(xué)質(zhì)量的提升也具有促進(jìn)作用。

1 Dijkstra算法的一般步驟

設(shè)圖

G

=(

P

,

E

)為一個(gè)帶權(quán)無(wú)向圖(或?yàn)橛邢驁D,本文主要討論無(wú)向圖),

P

為結(jié)點(diǎn)集,

E

為邊集。Dijkstra算法的一般步驟如下:Step 1:給定初值,令

A

={

p

},

d

(

p

)=0,

B

=

P

-

A

。若

p

與

B

中的結(jié)點(diǎn)有邊直接相連,則記為正常權(quán)值,否則其權(quán)值記為∞;Step 2:計(jì)算

p

與

B

中結(jié)點(diǎn)的距離,然后選取一個(gè)距離最短的結(jié)點(diǎn)

p

。此時(shí),

A

=

A

∪{

p

},

B

=

V

-

A

;Step 3:以

p

作為新的中間點(diǎn),繼續(xù)計(jì)算

p

與

B

中結(jié)點(diǎn)的距離,尋找距離最短的結(jié)點(diǎn)

p

。若從

p

到結(jié)點(diǎn)

p

的距離(經(jīng)過(guò)結(jié)點(diǎn)

p

)比不經(jīng)過(guò)結(jié)點(diǎn)

p

短,則更新結(jié)點(diǎn)

p

的距離值,否則不更新;Step 4:若

B

=?,則停止,否則轉(zhuǎn)Step 2繼續(xù)尋找。用上述步驟1-4計(jì)算的距離

d

(

p

)即是

p

到

p

的最短路的權(quán),由

p

的父親標(biāo)記向回追溯到

p

, 即可得

p

到

p

的最短路徑。下面將從不同角度對(duì)Dijkstra算法進(jìn)行教學(xué)探析。

2 實(shí)例教學(xué)探析

2.1 實(shí)例1

表示結(jié)點(diǎn)為

p

(

i

=0,1,…,5)的帶權(quán)無(wú)向圖如圖1所示。每個(gè)結(jié)點(diǎn)代表一個(gè)城市,結(jié)點(diǎn)間連線上的數(shù)字表示城市之間的距離。試用Dijkstra算法計(jì)算

p

到

p

(

i

=1,…,5)的最短路徑和距離。

圖1 6個(gè)城市的道路圖

(1)表上作業(yè)法。可將Dijkstra算法步驟用表格列出,具體過(guò)程如表1所列。表1中每一行用帶方框標(biāo)識(shí)的數(shù)字表示在迭代過(guò)程中尋找路徑權(quán)的最小值。最短路徑可表示為該最小數(shù)字首次出現(xiàn)前的最短路徑加上該結(jié)點(diǎn)組成。

表1 表上作業(yè)過(guò)程

(2)圖上標(biāo)號(hào)法。Dijkstra算法的結(jié)果也可在圖上用標(biāo)號(hào)(

i

,

d

)標(biāo)出。其中,

d

表示從源點(diǎn)

p

到結(jié)點(diǎn)

p

的最短路的權(quán);

i

表示

p

的父親點(diǎn),用以追溯最短路徑。每次迭代都會(huì)得到一個(gè)新的永久標(biāo)號(hào),最終將會(huì)得到一棵以

p

為根的生成樹(shù)從而得到任意一個(gè)結(jié)點(diǎn)與根結(jié)點(diǎn)

p

之間的最短路徑。具體尋找過(guò)程,如圖2(a)圖2(f)所示,圖中的粗實(shí)線表示尋找到的最短路徑。

圖2 圖上標(biāo)號(hào)過(guò)程

2.2 實(shí)例2

某化工廠為了保障正常生產(chǎn),需要對(duì)26個(gè)巡檢點(diǎn)進(jìn)行例行巡檢,且要求巡檢工人從調(diào)度中心(22)開(kāi)始巡檢,詳細(xì)的巡檢路線圖,如圖3所示。試給出巡檢人員從調(diào)動(dòng)中心(22)到其余巡檢點(diǎn)的最短路徑。

圖3 工廠巡檢路線圖

利用Dijkstra算法可求得巡檢中心22到其余巡檢點(diǎn)的最短路。由于巡檢點(diǎn)較多,使用流程表法較繁瑣,而表上作業(yè)法所需表格較大,可考慮圖上標(biāo)號(hào)法。圖上標(biāo)號(hào)的開(kāi)始如圖4左圖所示,結(jié)束如圖4右圖所示,中間標(biāo)號(hào)過(guò)程省略。圖4(右圖)中的粗實(shí)線即是用圖上標(biāo)號(hào)法得到的從巡檢中心22到其余各點(diǎn)最短路的生成樹(shù),具體的最短路徑和距離,如表2所列。

圖4 圖上標(biāo)號(hào)法的開(kāi)始(左圖)和結(jié)束(右圖)

表2 最短路徑和最短距離

3 結(jié)束語(yǔ)

本文分別運(yùn)用表上作業(yè)法和圖上標(biāo)號(hào)法對(duì)Dijkstra算法進(jìn)行了教學(xué)探析,但每種方法都有優(yōu)缺點(diǎn)。圖上標(biāo)號(hào)法雖然簡(jiǎn)潔明了,但由于新老標(biāo)號(hào)不斷更新,需集中精力、保持清醒的頭腦才不會(huì)出錯(cuò)。表上作業(yè)法可以在表上直接進(jìn)行迭代，比圖上標(biāo)號(hào)法更具有秩序性和規(guī)則性,較適合復(fù)雜問(wèn)題的推算,但結(jié)點(diǎn)個(gè)數(shù)較多時(shí),所需表格會(huì)非常大。若結(jié)點(diǎn)個(gè)數(shù)非常多,可考慮MATLAB編程方法解決,但MATLAB編程要求學(xué)生具備一定的編程基礎(chǔ)。此外,在高職數(shù)學(xué)教學(xué)中適當(dāng)引入數(shù)學(xué)建模競(jìng)賽試題(如實(shí)例2)將有助于提升學(xué)生對(duì)數(shù)學(xué)的學(xué)習(xí)興趣和應(yīng)用意識(shí),同時(shí)也有助于培養(yǎng)學(xué)生的發(fā)散性創(chuàng)新思維和動(dòng)手實(shí)踐能力。