離散數(shù)學(xué)-最短路徑問題課件

1

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

1例:如下圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字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從v1到v6的路線是很多的。比如從v1出發(fā)，經(jīng)過v3一、問題的提法及應(yīng)用背景

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

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

如果圖中各點(diǎn)表示各個(gè)城市，邊表示城市間的公路，這就是一個(gè)公路交通網(wǎng)絡(luò)圖，如果從a點(diǎn)出發(fā)，目的地是z，那么如何尋求一條自點(diǎn)a到z的通路，使通路上各邊的權(quán)之和最小，這就是賦權(quán)圖的最短通路問題。5如果圖中各點(diǎn)表示各個(gè)城市，邊表示城市間的公6三、賦權(quán)圖的最短通路基本思想：先求出a到某一點(diǎn)的最短通路，然后利用這個(gè)結(jié)果再去確定a到另一點(diǎn)的最短通路，如此下去，直到找到a到z的最短通路為止。6三、賦權(quán)圖的最短通路基本思想：先求出a到某一點(diǎn)的最短通路，7若取T={e,f,g,z}，點(diǎn)e關(guān)于T的指標(biāo)DT(e)就是由a到e但不通過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但不通過目標(biāo)集T中其他點(diǎn)的所有通路中各邊權(quán)之和（簡稱為通路權(quán)和）的最小者稱為點(diǎn)t關(guān)于T的指標(biāo)，記為DT(t)。7若取T={e,f,g,z}，點(diǎn)e關(guān)于T的指標(biāo)DT(e)就是8用窮舉法可得：a到e但不通過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用窮舉法可得：a到e但不通過T中其他點(diǎn)（即f,g,z）a9對(duì)于目標(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，對(duì)于點(diǎn)z，由于不存在a到z但不通過T中其它點(diǎn)的通路，約定。比較T中四個(gè)點(diǎn)的指標(biāo)可知：點(diǎn)f的指標(biāo)最小，因此可得：a到f的最短通路權(quán)和為DT(f)=6。9對(duì)于目標(biāo)集T={e,f,g,z}，已用窮舉法得到e關(guān)于T的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是目的地z，則問題得解。如果t1不是目的地z，則把t1從T中挖去，得到新的目標(biāo)集T1，即T1=T-{t1}對(duì)于T1，又求出其各點(diǎn)的指標(biāo)，并確定最小指標(biāo)點(diǎn)，如果這個(gè)最小指標(biāo)點(diǎn)就是目的地z，則問題得解。如果不是目的地z，則把在T1中又挖去這個(gè)最小指標(biāo)點(diǎn)，得到新的目標(biāo)集T2，不斷重復(fù)上述過程，直到目的地z為某個(gè)目標(biāo)集的最小指標(biāo)點(diǎn)為止。由此可見，求最短通路問題的關(guān)鍵是：如何求目標(biāo)集中各點(diǎn)的指標(biāo)。10一般地，設(shè)T={t1,t2,…,tn}，其中t1為11

以上用窮舉法求目標(biāo)集中各點(diǎn)的指標(biāo)，思路簡單，但方法不可取,特別是圖中的點(diǎn)較多時(shí)。下面介紹用遞推的方法來求目標(biāo)集中各點(diǎn)的指標(biāo)。11以上用窮舉法求目標(biāo)集中各點(diǎn)的指標(biāo)，思路簡單，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,對(duì)于T1中與t1鄰接的點(diǎn)t,當(dāng)尋求這點(diǎn)t的指標(biāo)時(shí),將a到t1的最短通路再加上邊t1t所組成的通路,也是一條由a到t但不通過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).對(duì)于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如果已經(jīng)求得目標(biāo)集T={t1,t2,…,tn}中各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設(shè)T={e,f,g,z}，已用窮舉法求得DT(e)=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例1用狄克斯特洛算法求下列圖中a到z的最短通路。比較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（2）令T2=T1-={c,d,e,f,g,z}，16（3）令T3=T2-fthxbt5={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（3）令T3=T2-zp5x5ff={c,e,f,g,z}，T317（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（4）令T4=T3-{c}={e,f,g,z}，T4中各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（5）令T5=T4-{f}={e,g,z}，T5中各點(diǎn)的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(DT5(z),DT5(e)+W(e,z))=min(10,6+3)