離散數(shù)學(xué)-最短路徑問題市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)

1

例:以下列圖所表示單行線交通網(wǎng)，每個(gè)弧旁邊數(shù)字表示這條單行線長度。現(xiàn)在有一個(gè)人要從v1出發(fā)，經(jīng)過這個(gè)交通網(wǎng)抵達(dá)v6，要尋求總路程最短線路。v6v5v3v1v4v2365112436最短路徑問題

第1頁2

從v1到v6路線是很多。比如從v1出發(fā)，經(jīng)過v2,v4抵達(dá)v6或者從v1出發(fā)，經(jīng)過v2，v3，v5抵達(dá)v6等等。但不一樣路線，經(jīng)過總長度是不一樣。比如，按照第一個(gè)線路，總長度是3+6+3=12單位，按照第二個(gè)路線，總長度是3+1+1+6=11單位。第2頁3一、問題提法及應(yīng)用背景

（1）問題提法——尋求網(wǎng)絡(luò)中兩點(diǎn)間最短路就是尋求連接這兩個(gè)點(diǎn)邊總權(quán)數(shù)為最小通路。

（2）應(yīng)用背景——管道鋪設(shè)、交通網(wǎng)絡(luò)、線路安排、廠區(qū)布局、設(shè)備更新等。第3頁4在圖點(diǎn)或邊上表明某種信息數(shù)稱為權(quán)。含有權(quán)圖稱為賦權(quán)圖。二、賦權(quán)圖定義如圖第4頁5

假如圖中各點(diǎn)表示各個(gè)城市，邊表示城市間公路，這就是一個(gè)公路交通網(wǎng)絡(luò)圖，假如從a點(diǎn)出發(fā)，目標(biāo)地是z，那么怎樣尋求一條自點(diǎn)a到z通路，使通路上各邊權(quán)之和最小，這就是賦權(quán)圖最短通路問題。第5頁6三、賦權(quán)圖最短通路基本思想：先求出a到某一點(diǎn)最短通路，然后利用這個(gè)結(jié)果再去確定a到另一點(diǎn)最短通路，如此下去，直到找到a到z最短通路為止。第6頁7若取T={e,f,g,z}，點(diǎn)e關(guān)于T指標(biāo)DT(e)就是由a到e但不經(jīng)過T中其

他點(diǎn)（即f,g,z）全部通路中權(quán)和最小者。目標(biāo)集——設(shè)V是圖點(diǎn)集，T是V子集，且T含有目標(biāo)z但不含有a，則稱T為目標(biāo)集。指標(biāo)——在目標(biāo)集T中任取一點(diǎn)t，由a到t但不經(jīng)過目標(biāo)集T中其它點(diǎn)全部通路中各邊權(quán)之和（簡稱為通路權(quán)和）最小者稱為點(diǎn)t關(guān)于T指標(biāo)，記為DT(t)。第7頁8用窮舉法可得：a到e但不經(jīng)過T中其它點(diǎn)（即f,g,z）通路有：abe權(quán)和為10abce權(quán)和為9ace權(quán)和為10acbe權(quán)和為15adcbe權(quán)和為18adce權(quán)和為13由此可見：e關(guān)于T指標(biāo)DT(e)=9如圖第8頁9對于目標(biāo)集T={e,f,g,z}，已用窮舉法得到e關(guān)于T指標(biāo)DT(e)=9，一樣用窮舉法可得f關(guān)于T指標(biāo)DT(f)=6,g關(guān)于T指標(biāo)DT(g)=8，對于點(diǎn)z，因?yàn)椴淮嬖赼到z但不經(jīng)過T中其它點(diǎn)通路，約定。比較T中四個(gè)點(diǎn)指標(biāo)可知：點(diǎn)f指標(biāo)最小，所以可得：a到f最短通路權(quán)和為DT(f)=6。第9頁10普通地，設(shè)T={t1,t2,…,tn}，其中t1為T中指標(biāo)最小點(diǎn)，即DT(t1)=min(DT(t1),DT(t2),…DT(tn))則a到t1最短通路權(quán)和就是DT(t1)。當(dāng)?shù)玫侥繕?biāo)集T中最小指標(biāo)點(diǎn)t1后，假如t1是目標(biāo)地z，則問題得解。假如t1不是目標(biāo)地z，則把t1從T中挖去，得到新目標(biāo)集T1，即T1=T-{t1}對于T1，又求出其各點(diǎn)指標(biāo)，并確定最小指標(biāo)點(diǎn)，假如這個(gè)最小指標(biāo)點(diǎn)就是目標(biāo)地z，則問題得解。假如不是目標(biāo)地z，則把在T1中又挖去這個(gè)最小指標(biāo)點(diǎn)，得到新目標(biāo)集T2，不停重復(fù)上述過程，直到目標(biāo)地z為某個(gè)目標(biāo)集最小指標(biāo)點(diǎn)為止。由此可見，求最短通路問題關(guān)鍵是：怎樣求目標(biāo)集中各點(diǎn)指標(biāo)。第10頁11

以上用窮舉法求目標(biāo)集中各點(diǎn)指標(biāo)，思緒簡單，但方法不可取,尤其是圖中點(diǎn)較多時(shí)。下面介紹用遞推方法來求目標(biāo)集中各點(diǎn)指標(biāo)。第11頁12假如已經(jīng)求得目標(biāo)集T={t1,t2,…,tn}中各點(diǎn)指標(biāo),設(shè)t1為T中指標(biāo)最小點(diǎn)，那么能推出T1=T-{t1}中各點(diǎn)指標(biāo).只須注意到t1已不屬于目標(biāo)集T1,對于T1中與t1鄰接點(diǎn)t,當(dāng)尋求這點(diǎn)t指標(biāo)時(shí),將a到t1最短通路再加上邊t1t所組成通路,也是一條由a到t但不經(jīng)過T1中其它點(diǎn)全部通路.所以t關(guān)于T1指標(biāo)

DT1(t)=min(DT(t),DT(t1)+W(t1,t))其中W(t1,t)是邊t1,t上權(quán).對于T1中與t1不鄰接點(diǎn)t2,那么它指標(biāo)沒有發(fā)生改變,即DT1(t2)=DT(t2)當(dāng)t1和t2不鄰接時(shí),令W(t1,t2)=∞,則t2關(guān)于T1指標(biāo)也寫作

DT1(t2)=min(DT(t2),DT(t1)+W(t1,t2))第12頁13設(shè)T={e,f,g,z}，已用窮舉法求得DT(e)=9，DT(f)=6,DT(g)=8，DT(g)=∞,其中f是最小指標(biāo)點(diǎn),于是可得到T1=T-{f}={e,g,z}各點(diǎn)指標(biāo):比如:如圖DT1(e)=min(DT(e),DT(f)+W(f,e))=min(9,6+2)=8DT1(g)=min(DT(g),DT(f)+W(f,g))=min(8,6+6)=8DT1(z)=min(DT(z),DT(f)+W(f,z))=min(∞,6+4)=10由以上分析可知:當(dāng)含有n個(gè)點(diǎn)目標(biāo)集Tn各點(diǎn)指標(biāo)求得時(shí),就能推出n-1個(gè)點(diǎn)目標(biāo)集Tn-1=Tn-{t1}(t1是T最小指標(biāo))各點(diǎn)指標(biāo).而初始情況目標(biāo)集T1=V-{a}各點(diǎn)指標(biāo)輕易求得,所以求點(diǎn)指標(biāo)問題處理.第13頁14例1用狄克斯特洛算法求以下圖中a到z最短通路。比較以上各點(diǎn)指標(biāo)可知，b是最小指標(biāo)點(diǎn)。但b不是目標(biāo)點(diǎn)，所以挖去b,于是可得：解（1）首先取目標(biāo)集T1={b,c,d,e,f,g,z}，T1中各點(diǎn)指標(biāo)為：

DT1(b)=2,(ab)DT1(c)=4,(ac)DT1(d)=3,(ad)DT1(e)=DT1(f)=DT1(g)=DT1(z)=∞第14頁15（2）令T2=T1-={c,d,e,f,g,z}，T2中各點(diǎn)指標(biāo)為：DT2(f)=min(DT1(f),DT1(b)+W(b,f))=min(∞,∞)=∞D(zhuǎn)T2(g)=min(DT1(g),DT1(b)+W(b,g))=min(∞,∞)=∞D(zhuǎn)T2(z)=min(DT1(z),DT1(b)+W(b,z))=min(∞,∞)=∞比較以上各點(diǎn)指標(biāo)可知，d是最小指標(biāo)點(diǎn)。但d不是目標(biāo)點(diǎn)，所以挖去d,于是可得：DT2(c)=min(DT1(c),DT1(b)+W(b,c))=min(4,2+3)=4(ac)DT2(d)=min(DT1(d),DT1(b)+W(b,d))=min(3,∞)=3(ad)DT2(e)=min(DT1(e),DT1(b)+W(b,e))=min(∞,2+6)=8(abe)第15頁16（3）令T3=T2-pxvp5df={c,e,f,g,z}，T3中各點(diǎn)指標(biāo)為：DT3（z）=min(DT2(z),DT2(d)+W(d,z))=min(∞,∞)=∞比較以上各點(diǎn)指標(biāo)可知，c是最小指標(biāo)點(diǎn)。但c不是目標(biāo)點(diǎn)，所以挖去c,于是可得：DT3（c）=min(DT2(c),DT2(d)+W(c,d))=min(4,3+2)=4(ac)DT3（e）=min(DT2(e),DT2(d)+W(d,e))=min(8,∞)=8(abe)DT3（f）=min(DT2(f),DT2(d)+W(d,f))=min(∞,3+2)=5(adf)DT3（g）=min(DT2(g),DT2(d)+W(d,g))=min(∞,3+7)=10(adg)第16頁17（4）令T4=T3-{c}={e,f,g,z}，T4中各點(diǎn)指標(biāo)為：DT4（z）=min(DT3(z),DT3(c)+W(c,z))=min(∞,∞)=∞比較以上各點(diǎn)指標(biāo)可知，f是最小指標(biāo)點(diǎn)。但f不是目標(biāo)點(diǎn)，所以挖去f,于是可得：DT4（e）=min(DT3(e),DT3(c)+W(c,e))=min(8,4+2)=6(ace)DT4（f）=min(DT3(f),DT3(c)+W(c,f))=min(5,4+6)=5(adf)DT4（g）=min(DT3(g),DT3(c)+W(c,g))=min(10,4+7)=10(adg)第17頁18（5）令T5=T4-{f}={e,g,z}，T5中各點(diǎn)指標(biāo)為：比較以上各點(diǎn)指標(biāo)可知，e是最小指標(biāo)點(diǎn)。但不是目標(biāo)點(diǎn)，所以挖去e,于是可得：DT5（e）=min(DT4(e),DT4(f)+W(f,e))=min(6,5+1)=6(ace或adfe)DT5（g）=min(DT4(g),DT4(f)+W(f,g))=min(10,5+6)=10(adg)DT5（z）=min(DT4(z),DT4(f)+W(f,z))=min(∞,5+5)=10(adfz)第18頁19（6）令T6=T5-{e}={g,z}，T6中各點(diǎn)指標(biāo)為：DT6（g）=min(DT5(g),DT5(e)+W(e,g))=min(10,∞)=10(adg)DT6（z）=min(DT