最短路問題PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1最短路問題最短路問題 第1頁/共52頁 第2頁/共52頁 第3頁/共52頁 第4頁/共52頁例例2: 某兩人有一只某兩人有一只8升的酒壺裝滿了酒，還有兩升的酒壺裝滿了酒，還有兩只空壺，分別為只空壺，分別為5升和升和3升升.現(xiàn)要將酒平分，求最少現(xiàn)要將酒平分，求最少的操作次數(shù)的操作次數(shù).解解 設(shè)設(shè)x1,x2,x3分別表示分別表示8,5,3升酒壺中的酒量升酒壺中的酒量.則則1231238,8,5,3.xxxxxx容易算出容易算出(x1,x2,x3) 的組合形式共的組合形式共24種種.(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,2);(2,3,3); (3,5,0

2、);(3,4,1);(3,3,2);(3,2,3);(4,4,0);(4,3,1);(4,2,2);(4,1,3);(5,3,0);(5,2,1);(5,1,2);(5,0,3);(6,2,0);(6,1,1);(6,0,2);(7,1,0);(7,0,1);(8,0,0);第5頁/共52頁于是問題轉(zhuǎn)化為在該圖中求于是問題轉(zhuǎn)化為在該圖中求 (8,0,0)到到(4,4,0)的一條最的一條最短路短路(求最短路的算法在有向圖中仍適用求最短路的算法在有向圖中仍適用).結(jié)果如下：結(jié)果如下：(8,0,0)(3,5,0)(3,2,3)(6,2,0)(6,0,2)(1,5, 2)(1,4,3)(4,4,0).

3、 每種組合用一個(gè)點(diǎn)表示，若點(diǎn)每種組合用一個(gè)點(diǎn)表示，若點(diǎn)u能通過倒酒的方式變能通過倒酒的方式變換為換為v,則則 u向向v 連有向邊，并將各邊賦權(quán)連有向邊，并將各邊賦權(quán)1，得一個(gè)有向，得一個(gè)有向賦權(quán)圖賦權(quán)圖.第6頁/共52頁 第7頁/共52頁 第8頁/共52頁 這一節(jié)介紹一種求有向圖上最短有向路的方這一節(jié)介紹一種求有向圖上最短有向路的方法，叫做法，叫做標(biāo)號(hào)法。標(biāo)號(hào)法。3.2 求最短有向路的標(biāo)號(hào)法求最短有向路的標(biāo)號(hào)法 所謂標(biāo)號(hào)所謂標(biāo)號(hào),我們是指與圖的每一個(gè)頂點(diǎn)對(duì)應(yīng)的一個(gè)我們是指與圖的每一個(gè)頂點(diǎn)對(duì)應(yīng)的一個(gè)數(shù)數(shù)(或幾個(gè)數(shù)或幾個(gè)數(shù))例如設(shè)例如設(shè)G=(V,A)的頂點(diǎn)集合是的頂點(diǎn)集合是V=v1,v2, ,vn

4、，如果我們能使，如果我們能使v1對(duì)應(yīng)一個(gè)數(shù)對(duì)應(yīng)一個(gè)數(shù)b(1)，v2對(duì)應(yīng)數(shù)對(duì)應(yīng)數(shù)b(2)，vn對(duì)應(yīng)數(shù)對(duì)應(yīng)數(shù)b(n)，那么，這些數(shù)，那么，這些數(shù)b(i)就稱為就稱為vi的標(biāo)號(hào)，當(dāng)然，在不同的問題中，標(biāo)號(hào)的標(biāo)號(hào)，當(dāng)然，在不同的問題中，標(biāo)號(hào)b(i)一般代表一般代表不同的意義不同的意義.第9頁/共52頁 第10頁/共52頁第11頁/共52頁 第12頁/共52頁 第13頁/共52頁第14頁/共52頁 現(xiàn)在來討論標(biāo)號(hào)法好不好？要回答這個(gè)問題現(xiàn)在來討論標(biāo)號(hào)法好不好？要回答這個(gè)問題, ,首先應(yīng)該明確一下什么叫首先應(yīng)該明確一下什么叫“好好”, ,什么叫什么叫“不好不好”一般說來，主要的好壞標(biāo)準(zhǔn)是計(jì)算起來快不快不一

5、般說來，主要的好壞標(biāo)準(zhǔn)是計(jì)算起來快不快不快快( (還有比的標(biāo)準(zhǔn)，例如容不容易拿上計(jì)算機(jī)計(jì)算還有比的標(biāo)準(zhǔn)，例如容不容易拿上計(jì)算機(jī)計(jì)算；是否易于普及等等；是否易于普及等等) )，或者說，用這個(gè)方法計(jì)算，或者說，用這個(gè)方法計(jì)算時(shí)，需要進(jìn)行的運(yùn)算次數(shù)多不多時(shí)，需要進(jìn)行的運(yùn)算次數(shù)多不多. .當(dāng)然，運(yùn)算次數(shù)當(dāng)然，運(yùn)算次數(shù)越少越好越少越好. .3.3 標(biāo)號(hào)法好不標(biāo)號(hào)法好不好好第15頁/共52頁 大家也許會(huì)說，運(yùn)算次數(shù)多少不完全決定于采大家也許會(huì)說，運(yùn)算次數(shù)多少不完全決定于采用什么方法，還和要解決的問題有關(guān)同樣用標(biāo)用什么方法，還和要解決的問題有關(guān)同樣用標(biāo)號(hào)法，解一個(gè)只有號(hào)法，解一個(gè)只有10個(gè)頂點(diǎn)的問題可能只要

6、進(jìn)行個(gè)頂點(diǎn)的問題可能只要進(jìn)行幾千次運(yùn)算，而解一個(gè)幾千次運(yùn)算，而解一個(gè)100個(gè)頂點(diǎn)的問題，就可能個(gè)頂點(diǎn)的問題，就可能要進(jìn)行幾百萬次運(yùn)算了，這又怎么比較呢？要進(jìn)行幾百萬次運(yùn)算了，這又怎么比較呢？ 辦法還是有的辦法還是有的.那就是，設(shè)圖那就是，設(shè)圖G有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)(為了為了簡(jiǎn)單起見，我們就不研究邊數(shù)簡(jiǎn)單起見，我們就不研究邊數(shù)m的影響了的影響了),我們來我們來估計(jì)一下，把標(biāo)號(hào)法用到圖估計(jì)一下，把標(biāo)號(hào)法用到圖G上去需要進(jìn)行幾次運(yùn)上去需要進(jìn)行幾次運(yùn)算算.當(dāng)然，這樣估計(jì)出來的結(jié)果不會(huì)是一個(gè)確定的當(dāng)然，這樣估計(jì)出來的結(jié)果不會(huì)是一個(gè)確定的數(shù)數(shù),而是象而是象n2,3n3+4n2,2n等等這樣的與等等這樣的與n

7、有關(guān)的數(shù)有關(guān)的數(shù),即即n的函數(shù)的函數(shù).然后再以這種函數(shù)為標(biāo)準(zhǔn)來比較方法的好然后再以這種函數(shù)為標(biāo)準(zhǔn)來比較方法的好壞壞.比如說，有兩種方法，第一種要進(jìn)行比如說，有兩種方法，第一種要進(jìn)行n3次加法次加法，而第二種要進(jìn)行，而第二種要進(jìn)行n5次加法，當(dāng)然第一種就比第二次加法，當(dāng)然第一種就比第二種好，因?yàn)樵诜N好，因?yàn)樵趎較大時(shí)，較大時(shí)，n5比比n3要大多了要大多了.第16頁/共52頁 上面講的是怎樣比較兩種方法誰好誰壞上面講的是怎樣比較兩種方法誰好誰壞.現(xiàn)在總共現(xiàn)在總共只講了一個(gè)標(biāo)號(hào)法，又怎么評(píng)論它的好壞呢？也有辦只講了一個(gè)標(biāo)號(hào)法，又怎么評(píng)論它的好壞呢？也有辦法的法的.目前一般認(rèn)為，如果一種方法所需要的運(yùn)

8、算次數(shù)目前一般認(rèn)為，如果一種方法所需要的運(yùn)算次數(shù)能表示成能表示成n的多項(xiàng)式，例如的多項(xiàng)式，例如n4,2n2+3n等等等等.這種方法就這種方法就認(rèn)為是好的，或者說是有效的認(rèn)為是好的，或者說是有效的.而如果一種方法的計(jì)算而如果一種方法的計(jì)算次數(shù)是某一個(gè)數(shù)的次數(shù)是某一個(gè)數(shù)的n次冪，例如次冪，例如2n,10n，即是，即是n的指數(shù)函的指數(shù)函數(shù)，這種方法就認(rèn)為是不好的，或者說是無效的數(shù)，這種方法就認(rèn)為是不好的，或者說是無效的.請(qǐng)看請(qǐng)看如下這張表：如下這張表：n5102030501001000方法A(運(yùn)算次數(shù)n3)6251000800027000 625000106109方法B(運(yùn)算次數(shù)2n)3210241

9、061091015103010300第17頁/共52頁上表中對(duì)一種需要進(jìn)行上表中對(duì)一種需要進(jìn)行n3次運(yùn)算的方法次運(yùn)算的方法A與另一種需要進(jìn)與另一種需要進(jìn)行行2n次運(yùn)算的方法次運(yùn)算的方法B進(jìn)行了比較進(jìn)行了比較(關(guān)于關(guān)于2n的近似值的近似值,我們是我們是以以210=1024103來估算的來估算的,例如例如250=(210)5(103)5=1015).從上從上表可以看出，方法表可以看出，方法B的運(yùn)算次數(shù)的增長(zhǎng)速度是驚人的的運(yùn)算次數(shù)的增長(zhǎng)速度是驚人的.也也許有的人會(huì)認(rèn)為，現(xiàn)在反正有大型計(jì)算機(jī)，計(jì)算次數(shù)多許有的人會(huì)認(rèn)為，現(xiàn)在反正有大型計(jì)算機(jī)，計(jì)算次數(shù)多一些無所謂一些無所謂.其實(shí)不然其實(shí)不然.例如我們有一

10、個(gè)每秒能計(jì)算一百萬例如我們有一個(gè)每秒能計(jì)算一百萬次的計(jì)算機(jī)，那么，在次的計(jì)算機(jī)，那么，在1000秒內(nèi)可以進(jìn)行秒內(nèi)可以進(jìn)行10001000000=109次次(即十億次即十億次)運(yùn)算運(yùn)算,如果用方法如果用方法A,則則則則可以解決一個(gè)可以解決一個(gè)1000個(gè)頂點(diǎn)的問題，而用方法個(gè)頂點(diǎn)的問題，而用方法B呢？卻只能呢？卻只能解決一個(gè)解決一個(gè)30個(gè)頂點(diǎn)的問題個(gè)頂點(diǎn)的問題.如果想用方法如果想用方法B來解決一個(gè)來解決一個(gè)100個(gè)頂點(diǎn)的問題，即使用的是每秒能計(jì)算一億次的計(jì)算機(jī)個(gè)頂點(diǎn)的問題，即使用的是每秒能計(jì)算一億次的計(jì)算機(jī)，也需要，也需要1022秒，即要好幾萬億年秒，即要好幾萬億年.第18頁/共52頁 從上面的簡(jiǎn)

11、單比較久可以看出，為什么說計(jì)算從上面的簡(jiǎn)單比較久可以看出，為什么說計(jì)算次數(shù)是次數(shù)是n的多項(xiàng)式的方法是有效的，而計(jì)算次數(shù)是的多項(xiàng)式的方法是有效的，而計(jì)算次數(shù)是n的指數(shù)函數(shù)的方法是無效的的指數(shù)函數(shù)的方法是無效的.另外，也可以看出，另外，也可以看出，單靠提高計(jì)算機(jī)的速度還不夠，還必須從數(shù)學(xué)上單靠提高計(jì)算機(jī)的速度還不夠，還必須從數(shù)學(xué)上尋求有效的計(jì)算方法尋求有效的計(jì)算方法. 現(xiàn)在再回過頭來看看標(biāo)號(hào)法好不好現(xiàn)在再回過頭來看看標(biāo)號(hào)法好不好.回想一下標(biāo)回想一下標(biāo)號(hào)法的各輪計(jì)算，可以看出，它只包含兩種運(yùn)算號(hào)法的各輪計(jì)算，可以看出，它只包含兩種運(yùn)算：加法與比較大?。杭臃ㄅc比較大小(比較大小也需要花費(fèi)時(shí)間，所比較大

12、小也需要花費(fèi)時(shí)間，所以也要考慮以也要考慮).加法用于計(jì)算加法用于計(jì)算k(i,j)，每計(jì)算一個(gè)，每計(jì)算一個(gè)k(i,j)進(jìn)行一次加法，而且每一條弧最多只計(jì)算一次進(jìn)行一次加法，而且每一條弧最多只計(jì)算一次.因因此此,如果圖中有如果圖中有m條弧，那么至多進(jìn)行條弧，那么至多進(jìn)行m次加法次加法.對(duì)對(duì)于一個(gè)有于一個(gè)有n個(gè)頂點(diǎn)的簡(jiǎn)單有向圖來說，最多有個(gè)頂點(diǎn)的簡(jiǎn)單有向圖來說，最多有n(n-1)條弧條弧(假設(shè)從每一個(gè)頂點(diǎn)假設(shè)從每一個(gè)頂點(diǎn)vi出發(fā)，都有出發(fā)，都有n-1條弧指條弧指向其他的向其他的n-1個(gè)頂點(diǎn)個(gè)頂點(diǎn))，因此，最多進(jìn)行，因此，最多進(jìn)行n(n-1)次加次加法，放寬一點(diǎn)，也可以說，至多進(jìn)行法，放寬一點(diǎn)，也可以

13、說，至多進(jìn)行n2次加法次加法.第19頁/共52頁 另外，在每一輪計(jì)算中，在找使另外，在每一輪計(jì)算中，在找使k(i,j)達(dá)到最小達(dá)到最小的弧的弧時(shí)，要用到比較大小的運(yùn)算，一般說來時(shí)，要用到比較大小的運(yùn)算，一般說來，要從，要從s個(gè)數(shù)中把最小的數(shù)找出來，要進(jìn)行個(gè)數(shù)中把最小的數(shù)找出來，要進(jìn)行s-1次比次比較較(例如有四個(gè)數(shù)例如有四個(gè)數(shù)a1,a2,a3,a4，那么可以先拿，那么可以先拿a1與與a2比，然后拿這兩個(gè)數(shù)中小的數(shù)與比，然后拿這兩個(gè)數(shù)中小的數(shù)與a3比，再拿小的數(shù)比，再拿小的數(shù)與與a4比，比三次就能知道哪個(gè)數(shù)最小了比，比三次就能知道哪個(gè)數(shù)最小了).那么在每那么在每一輪的步驟一輪的步驟1中，一般會(huì)選

14、出幾條弧呢？算得寬一中，一般會(huì)選出幾條弧呢？算得寬一些，至多些，至多n2條吧條吧(事實(shí)上要少得多事實(shí)上要少得多)，因此至多進(jìn)行，因此至多進(jìn)行n2次比較，整個(gè)計(jì)算的輪數(shù)不會(huì)超過次比較，整個(gè)計(jì)算的輪數(shù)不會(huì)超過n，因此，總，因此，總起來說，至多進(jìn)行起來說，至多進(jìn)行n3次比較大小的運(yùn)算次比較大小的運(yùn)算. 通過上面的估計(jì)，可以得出這樣的結(jié)論：把標(biāo)通過上面的估計(jì)，可以得出這樣的結(jié)論：把標(biāo)號(hào)法用在一個(gè)號(hào)法用在一個(gè)n個(gè)頂點(diǎn)的圖上，至多進(jìn)行個(gè)頂點(diǎn)的圖上，至多進(jìn)行n2次加法次加法和和n3次比較大小次比較大小.因此，可以說，標(biāo)號(hào)法是一種好因此，可以說，標(biāo)號(hào)法是一種好的、有效的計(jì)算方法的、有效的計(jì)算方法.第20頁/共

15、52頁問題：?jiǎn)栴}：給定簡(jiǎn)單權(quán)圖給定簡(jiǎn)單權(quán)圖G = (V, E)，并設(shè)，并設(shè)G 有有n個(gè)頂個(gè)頂點(diǎn)，求點(diǎn)，求G中點(diǎn)中點(diǎn)u0到其它各點(diǎn)的最短路到其它各點(diǎn)的最短路.Dijkstra算法算法 (Edmonds, 1965)(2) 若若i = n-1，則停；否則令，則停；否則令 = V Si , iSiSiS 對(duì)每個(gè)對(duì)每個(gè)v ，令，令 l(v) = min l(v)，l(ui) + w(uiv)(1) 置置 l(u0) = 0；對(duì)所有；對(duì)所有vV u0，令，令 l(v) = ； S0 = u0，i = 0.3.4 求無向圖上的最短路的方法求無向圖上的最短路的方法第21頁/共52頁并用并用 ui+1記達(dá)到最

16、小值的某點(diǎn)記達(dá)到最小值的某點(diǎn).置置S i+1= Siu i+1，i = i+1（表示賦值語句，以后的算法中相同），轉(zhuǎn)（表示賦值語句，以后的算法中相同），轉(zhuǎn)（2）.終止后，終止后，u0 到到 v 的距離由的距離由 l(v) 的終值給出的終值給出.)(minvliSv (3) 計(jì)算計(jì)算說明：說明： （1） 算法中算法中w(uiv) 表示邊表示邊 uiv 的權(quán)；的權(quán)； （2） 若只想確定若只想確定u0到某頂點(diǎn)到某頂點(diǎn)v0的距離，的距離， 則當(dāng)某則當(dāng)某 uj 等于等于 v0 時(shí)即停；時(shí)即停；（3 3） 算法稍加改進(jìn)可同時(shí)得出算法稍加改進(jìn)可同時(shí)得出u u0 0到其它點(diǎn)的最短路到其它點(diǎn)的最短路. .第22

17、頁/共52頁例例3 求圖求圖 G 中中 u0 到其它點(diǎn)的距離到其它點(diǎn)的距離.u0 742155813G :解解 u0 742155813 （a）初始標(biāo)號(hào)）初始標(biāo)號(hào)第23頁/共52頁u0 742155813 2 4 7（b）用與）用與u0關(guān)聯(lián)的邊的關(guān)聯(lián)的邊的權(quán)權(quán)2,4,7分別更新與分別更新與u0相鄰相鄰的三個(gè)點(diǎn)的標(biāo)號(hào)的三個(gè)點(diǎn)的標(biāo)號(hào);（c）取小圓點(diǎn)中）取小圓點(diǎn)中標(biāo)號(hào)最小者得標(biāo)號(hào)最小者得 u1； u0 742155813 2 4 7u1 第24頁/共52頁（d）對(duì)與對(duì)與u1相鄰的小圓點(diǎn)，相鄰的小圓點(diǎn)，用用 l (u1) + w (u1v) = 2+1 = 3更新標(biāo)號(hào)更新標(biāo)號(hào)4； 2+5=7 更新兩個(gè)

18、更新兩個(gè)；u0 742155813 2 7 37 7u1 （e）取小圓點(diǎn)中標(biāo)號(hào)）取小圓點(diǎn)中標(biāo)號(hào) 最小者得最小者得 u2.u0 742155813 2 7 37 7u1 u2 第25頁/共52頁u4 u0 742155813 2 7 34 6（h）u1 u2 0u3u5 u0 742155813 2 7 37 7u1 u2 4 （f）u0 742155813 2 7 3 6u1 u2 （g）u0 742155813 2 7 34 6u1 u2 u3第26頁/共52頁3.5 圖的距離表圖的距離表 第27頁/共52頁 以下圖為例：這個(gè)圖有以下圖為例：這個(gè)圖有6個(gè)頂點(diǎn)，在圖個(gè)頂點(diǎn)，在圖3.5.2的的(

19、a)到到(f)中分別畫了以為起點(diǎn)的計(jì)算結(jié)中分別畫了以為起點(diǎn)的計(jì)算結(jié)果果.第28頁/共52頁第29頁/共52頁第30頁/共52頁第31頁/共52頁第32頁/共52頁第33頁/共52頁第34頁/共52頁 從上面的六張圖雖然可以查出任意一個(gè)頂點(diǎn)到另一從上面的六張圖雖然可以查出任意一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離，但是這樣畢竟不太方便個(gè)頂點(diǎn)的距離，但是這樣畢竟不太方便.比較方便的辦比較方便的辦法是把這些距離集中寫在一張象如下的表上在這張法是把這些距離集中寫在一張象如下的表上在這張表上，橫著排的一行數(shù)字叫做表上，橫著排的一行數(shù)字叫做“行行”，豎著排的一列，豎著排的一列數(shù)字叫做數(shù)字叫做“列列”.在表中的第在表中

20、的第1行上，寫的是從行上，寫的是從v1到各個(gè)到各個(gè)頂點(diǎn)的距離，同樣第頂點(diǎn)的距離，同樣第2行是行是v2到各頂點(diǎn)的距離，到各頂點(diǎn)的距離，.而而第第1列則是從各個(gè)頂點(diǎn)到列則是從各個(gè)頂點(diǎn)到v1的距離，其余各列也一樣的距離，其余各列也一樣.第35頁/共52頁 第36頁/共52頁n:n把帶權(quán)鄰接矩陣W作為距離矩陣的初值,即:n D(0)=(dij(0)pp=W第37頁/共52頁.是從vi到vj中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)度,因此:D(P)即是距離矩陣.第38頁/共52頁路徑時(shí),被記錄在R(k)中,依次求D(p)時(shí)求得R(p),可由R(p)來查找任何點(diǎn)對(duì)之間最短路的路由.)1()1()1()1()1()1()1(kkjkikkijkijkkjkikkijdddrdddk若若第39頁/共52頁kpippippipprprprk)(3)(2)(,21jrqrqrpjqpjqpjpm)(2)(1)(,11第40頁/共52頁第41頁/共52頁ikikijjknend第4