第6章并行算法的一般設(shè)計策略ppt課件

1、分布式系統(tǒng)開發(fā)計算機(jī)學(xué)院計算機(jī)科學(xué)與技術(shù)系計算機(jī)學(xué)院計算機(jī)科學(xué)與技術(shù)系主講：陳主講：陳 蕾蕾E-mail: chenleijx第六章第六章 并行算法的一般設(shè)計策略并行算法的一般設(shè)計策略6.1 串行算法的直接并行化串行算法的直接并行化6.2 從問題描述開始設(shè)計并行算法從問題描述開始設(shè)計并行算法6.3 借用已有算法求解新問題借用已有算法求解新問題6.4 串行算法的直接并行化補(bǔ)充實(shí)例串行算法的直接并行化補(bǔ)充實(shí)例:八皇后八皇后問題和單源最短路徑問題問題和單源最短路徑問題設(shè)計并行算法一般有設(shè)計并行算法一般有3種方法：種方法：（1檢查和開拓現(xiàn)有串行算法中固有的并行性，直檢查和開拓現(xiàn)有串行算法中固有的并行性

2、，直接將其并行化，該方法并不是對所有問題總是可行的，但接將其并行化，該方法并不是對所有問題總是可行的，但對很多應(yīng)用問題仍不失為一種有效的方法；對很多應(yīng)用問題仍不失為一種有效的方法；（2從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從頭設(shè)計一個全新的并行算法，這種方法有一定難度，但從頭設(shè)計一個全新的并行算法，這種方法有一定難度，但所設(shè)計的并行算法通常是高效的；所設(shè)計的并行算法通常是高效的；（3借助已有的并行算法求解新問題。借助已有的并行算法求解新問題。 方法描述方法描述發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造

3、為并行算法。將串行算法改造為并行算法。評注評注由串行算法直接并行化的方法是并行算法設(shè)由串行算法直接并行化的方法是并行算法設(shè)計的最常用方法之一；計的最常用方法之一；并非所有的串行算法都可以并行化；并非所有的串行算法都可以并行化；一個好的串行算法并不能并行化為一個好的一個好的串行算法并不能并行化為一個好的并行算法，相反一個不好的串行算法則有可并行算法，相反一個不好的串行算法則有可能產(chǎn)生很優(yōu)秀的并行算法，例如枚舉排序不能產(chǎn)生很優(yōu)秀的并行算法，例如枚舉排序不是一種好的串行算法。但是將其直接并行化是一種好的串行算法。但是將其直接并行化后可以得到比較好的并行算法后可以得到比較好的并行算法 ；顯著優(yōu)點(diǎn)：無需

4、考慮算法的穩(wěn)定性、收斂性顯著優(yōu)點(diǎn)：無需考慮算法的穩(wěn)定性、收斂性等復(fù)雜問題。等復(fù)雜問題。積分算法的直接并行化積分算法的直接并行化-的計算的計算0112341220044110.51i NdxxNiN 計算計算的串行的串行C代碼代碼#define N 1000000main() double local, pi = 0.0, w;long i;w=1.0/N;for (i = 0; iN; i +) local = (i + 0.5)*w;pi = pi + 4.0/(1.0+local * local);printf(“pi is %f n”, pi *w);k個處理器并行地計算部分和個處理器并

5、行地計算部分和計算計算的的MPI代碼代碼 # define N 100000 main ( ) double local=0.0，pi，w，temp=0.0； long i ，taskid，numtask； A：w=1.0/N； MPI_ Init(&argc，& argv)；/*MPI 初始化初始化*/ MPI _Comm _rank (MPI_COMM_WORLD，&taskid)；/*每個處理器確定各自每個處理器確定各自ID*/ MPI _Comm _Size (MPI_COMM_WORLD，&numtask)；/*每個處理器確定總處理每個處理器確定總處理

6、 器個數(shù)器個數(shù)*/ B： for (i= taskid； iaj thenk=k+1 end ifend for(3)bk= aiend forEnd枚舉排序的并行算法枚舉排序的并行算法對該算法的并行化是很簡單的，假設(shè)對一個長為對該算法的并行化是很簡單的，假設(shè)對一個長為n的輸?shù)妮斎胄蛄惺褂萌胄蛄惺褂胣個處理器進(jìn)行排序，只需每個處理器負(fù)責(zé)個處理器進(jìn)行排序，只需每個處理器負(fù)責(zé)完成對其中一個元素的定位，然后將所有的定位信息完成對其中一個元素的定位，然后將所有的定位信息集中到主進(jìn)程中，由主進(jìn)程負(fù)責(zé)完成所有元素的最終集中到主進(jìn)程中，由主進(jìn)程負(fù)責(zé)完成所有元素的最終排位。排位。 枚舉排序并行算法枚舉排序并行

7、算法輸入：無序數(shù)組輸入：無序數(shù)組a1an輸出：有序數(shù)組輸出：有序數(shù)組b1bnBegin(1) P0播送播送a1an給所有給所有Pi(2) for all Pi where 1in para-do (2.1)k=1 (2.2)for j = 1 to n doif (ai aj) or (ai = aj and ij) then k = k+1end if end for(3) P0收集收集k并按序定位并按序定位End 步驟步驟的時間復(fù)雜度為的時間復(fù)雜度為O On n）；步驟）；步驟中主進(jìn)中主進(jìn)程完成的數(shù)組元素重定位操作的時間復(fù)雜度為程完成的數(shù)組元素重定位操作的時間復(fù)雜度為O On n），通信復(fù)

8、雜度分別為），通信復(fù)雜度分別為O On n）；同時）；同時中的中的通信復(fù)雜度為通信復(fù)雜度為O On2n2）；所以總的計算復(fù)雜度為）；所以總的計算復(fù)雜度為O On n），總的通信復(fù)雜度為），總的通信復(fù)雜度為O On2n2）。）?？焖倥判蚩焖倥判騋uick Sort）快速排序快速排序Quick SortQuick Sort是一種最基本的排序算法是一種最基本的排序算法基本思想：在當(dāng)前無序區(qū)基本思想：在當(dāng)前無序區(qū)R1,nR1,n中取一個記錄作為比較的中取一個記錄作為比較的“基基準(zhǔn)準(zhǔn)”，用此基準(zhǔn)將當(dāng)前的無序區(qū)，用此基準(zhǔn)將當(dāng)前的無序區(qū)R1,nR1,n劃分成左右兩個無序的劃分成左右兩個無序的子區(qū)子區(qū)R1,i

9、-1R1,i-1和和Ri,n(1in)Ri,n(1in)，且左邊的無序子區(qū)中記錄，且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無序子區(qū)中記的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字。錄的所有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字?？焖倥判蛩惴ǖ男阅苤饕獩Q定于輸入數(shù)組的劃分是否均衡，而快速排序算法的性能主要決定于輸入數(shù)組的劃分是否均衡，而這與基準(zhǔn)元素的選擇密切相關(guān)。這與基準(zhǔn)元素的選擇密切相關(guān)。在最壞情況下，劃分的結(jié)果是一邊有在最壞情況下，劃分的結(jié)果是一邊有n-1n-1個元素，而另一邊有個元素，而另一邊有0 0個元素。如果每次遞歸排序中的劃

10、分都產(chǎn)生這種極度的不平衡，個元素。如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個算法的復(fù)雜度將是那么整個算法的復(fù)雜度將是n2n2）。在最好的情況下，每次）。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為O Onlognnlogn）。在一般的情況下該算法仍能保持）。在一般的情況下該算法仍能保持O Onlognnlogn的復(fù)的復(fù)雜度，只不過其具有更高的常數(shù)因子。雜度，只不過其具有更高的常數(shù)因子。 快速排序算法的串行實(shí)現(xiàn)快速排序算法的串行實(shí)現(xiàn)SISD上的快排序算法上的快排序算法 輸入：無序序列輸入：無序序列(Aq,A

11、r) 輸出：有序序列輸出：有序序列(Aq,Ar) Procedure QUICKSORTA, q, r） Begin if q 8 then OutputResult(chessboard)/* 結(jié)束遞歸并輸出結(jié)果結(jié)束遞歸并輸出結(jié)果 */ elsefor col = 1 to 8 do/* 判斷是否有列、對角線或反對角線沖突判斷是否有列、對角線或反對角線沖突 */（1no_collision = true（2i = 1（3while no_collision and i 0 do （2.1從某個從進(jìn)程從某個從進(jìn)程i接收信號接收信號signal （2.2if signal = Accomplis

12、hed then 從從進(jìn)程從從進(jìn)程i接收并記錄解接收并記錄解 end if （2.3if has_more_boards then ()向從進(jìn)程向從進(jìn)程i發(fā)送發(fā)送NewTask信號信號 ()向從進(jìn)程向從進(jìn)程i發(fā)送一個新棋盤發(fā)送一個新棋盤 else ()向從進(jìn)程向從進(jìn)程i發(fā)送發(fā)送Terminate信號信號 ()active_slaves = active_slaves - 1 end if end whileEnd /* EightQueensMaster */從進(jìn)程算法從進(jìn)程算法procedure EightQueenSlaveBegin（1向主進(jìn)程發(fā)送向主進(jìn)程發(fā)送Ready信號信號（2fin

13、ished = false（3while not finished do （3.1從主進(jìn)程接收信號從主進(jìn)程接收信號signal （3.2if signal = NewTask then ()從主進(jìn)程接收新棋盤從主進(jìn)程接收新棋盤 ()if 新棋盤合法新棋盤合法 then 在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送 給主進(jìn)程給主進(jìn)程 end if else /* signal = Terminate */finished = true end ifend whileEnd /* EightQueenSlave */附附2：單源最短路徑問題：單源最短路徑

14、問題單源最短路徑單源最短路徑(Single Source Shortest Path)問題是指求問題是指求從一個指定頂點(diǎn)從一個指定頂點(diǎn)s到其它所有頂點(diǎn)到其它所有頂點(diǎn)i之間的距離，因為是之間的距離，因為是單一頂點(diǎn)到其它頂點(diǎn)的距離，所以稱為單源。設(shè)圖單一頂點(diǎn)到其它頂點(diǎn)的距離，所以稱為單源。設(shè)圖G(V,E)是一個有向加權(quán)網(wǎng)絡(luò)，其中是一個有向加權(quán)網(wǎng)絡(luò)，其中V和和E分別為頂點(diǎn)集分別為頂點(diǎn)集合和邊集合，其邊權(quán)鄰接矩陣為合和邊集合，其邊權(quán)鄰接矩陣為W，邊上權(quán)值，邊上權(quán)值w(i,j) 0，i,jV，V=0,1,N-1。設(shè)設(shè)dist( i )為最短的路徑長度，即距離，其中為最短的路徑長度，即距離，其中sV且且i

15、s。這里采用著名的這里采用著名的Dijkstra算法，并將其并行化。算法，并將其并行化。最短路徑問題最短路徑問題用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：用帶權(quán)的有向圖表示一個交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)頂點(diǎn)表示城市表示城市邊邊表示城市間的交通聯(lián)系表示城市間的交通聯(lián)系權(quán)權(quán)表示此線路的長度或沿此線路運(yùn)輸所花的時間表示此線路的長度或沿此線路運(yùn)輸所花的時間或費(fèi)用等或費(fèi)用等問題：問題：從某頂點(diǎn)出發(fā)，沿圖中的邊是否有路可達(dá)另一頂點(diǎn)？從某頂點(diǎn)出發(fā)，沿圖中的邊是否有路可達(dá)另一頂點(diǎn)？若有多條路徑可達(dá)，則在所經(jīng)過的路徑中，各邊上權(quán)若有多條路徑可達(dá)，則在所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑值之和最小的一條路徑最短

16、路徑。最短路徑。問題提出問題提出兩種最常見的最短路徑算法：兩種最常見的最短路徑算法：求單源最短路徑的迪杰斯特拉求單源最短路徑的迪杰斯特拉DjikstraDjikstra算法和求所有算法和求所有頂點(diǎn)之間的最短路徑的弗洛伊德頂點(diǎn)之間的最短路徑的弗洛伊德FloydFloyd算法。算法。迪杰斯特拉算法迪杰斯特拉算法 0 02 24 41 170705 53 350501010353530303 315152020101015152020源源點(diǎn)點(diǎn)終終點(diǎn)點(diǎn)最短路徑最短路徑路徑長路徑長度度01（0,2,3,1）452（0,2）103（0,2,3）254（0,2,3,1,4）555把把V分成兩組：分成兩組：（

17、1S：存放已求得最短路徑的頂點(diǎn)的集合：存放已求得最短路徑的頂點(diǎn)的集合（2T=V-S：尚未確定最短路徑的頂點(diǎn)集合：尚未確定最短路徑的頂點(diǎn)集合將將T中頂點(diǎn)按最短路徑非遞減的次序加入到中頂點(diǎn)按最短路徑非遞減的次序加入到S中。中。迪杰斯特拉迪杰斯特拉Dijkstra算法思想：算法思想：這個過程中，總保持：這個過程中，總保持： 從源點(diǎn)從源點(diǎn)V0V0到到S S中各頂點(diǎn)的最短路徑長度都不大于從中各頂點(diǎn)的最短路徑長度都不大于從V0V0到到T T中任何頂點(diǎn)的最中任何頂點(diǎn)的最短路徑長度。短路徑長度。而且每個頂點(diǎn)對應(yīng)一個距離值：而且每個頂點(diǎn)對應(yīng)一個距離值：S S中頂點(diǎn)對應(yīng)的距離值，是從中頂點(diǎn)對應(yīng)的距離值，是從V0V

18、0到此頂點(diǎn)的最短路徑長度；到此頂點(diǎn)的最短路徑長度；T T中頂點(diǎn)對應(yīng)的距離值，是從中頂點(diǎn)對應(yīng)的距離值，是從V0V0到此頂點(diǎn)的只包括到此頂點(diǎn)的只包括S S中頂點(diǎn)作中間頂點(diǎn)中頂點(diǎn)作中間頂點(diǎn)的當(dāng)前最短路徑長度。的當(dāng)前最短路徑長度。單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 53 350501010353530303 315152020101015152020單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 53 350501010353530303 315152020101015152020單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 5

19、3 350501010353530303 315152020101015152020單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 53 350501010353530303 315152020101015152020單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 53 350501010353530303 315152020101015152020單源最短路徑圖例單源最短路徑圖例0 02 24 41 170705 53 350501010353530303 315152020101015152020迪杰斯特拉算法求單源最短路徑步驟：迪杰斯特拉算法求單源

20、最短路徑步驟：首先求得長度最短的一條最短路徑，再求得長度次短的一首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點(diǎn)到其它所有頂點(diǎn)之間條最短路徑，依此類推，直到從源點(diǎn)到其它所有頂點(diǎn)之間的最短路徑都已求得為止。的最短路徑都已求得為止。初始狀態(tài)下初始狀態(tài)下集合集合S中只有源點(diǎn)中只有源點(diǎn)v0，即：，即： S=v0，T=其余頂點(diǎn)其余頂點(diǎn)。T中頂點(diǎn)中頂點(diǎn)vi對應(yīng)的當(dāng)前最短路徑長度：對應(yīng)的當(dāng)前最短路徑長度： 若存在若存在，為，為弧上的權(quán)值弧上的權(quán)值w(v0,vi) 若不存在若不存在 ，為，為從從T T中選取一個當(dāng)前最短路徑長度最小的頂點(diǎn)中選取一個當(dāng)前最短路徑長度最小的頂點(diǎn)vk

21、vk加入加入S S。對對T T中剩余頂點(diǎn)中剩余頂點(diǎn)vivi的當(dāng)前最短路徑長度進(jìn)行修改：的當(dāng)前最短路徑長度進(jìn)行修改：若加進(jìn)若加進(jìn)vkvk作中間頂點(diǎn)，從作中間頂點(diǎn)，從v0v0到到vivi的距離值比不加的距離值比不加vkvk的路徑要短，則修改此距離值。的路徑要短，則修改此距離值。重復(fù)上述步驟，按照當(dāng)前最短路徑長度的非減次序產(chǎn)生重復(fù)上述步驟，按照當(dāng)前最短路徑長度的非減次序產(chǎn)生下一條最短路徑，并將該路徑的終點(diǎn)下一條最短路徑，并將該路徑的終點(diǎn)t tT T加入加入S S中，并中，并更新更新T T中剩余頂點(diǎn)的當(dāng)前最短路徑長度。中剩余頂點(diǎn)的當(dāng)前最短路徑長度。直到直到S SV V時即從源點(diǎn)時即從源點(diǎn)v0v0到其他

22、所有結(jié)點(diǎn)之間的最短路到其他所有結(jié)點(diǎn)之間的最短路徑都已求得為止），算法結(jié)束。徑都已求得為止），算法結(jié)束。選擇數(shù)據(jù)結(jié)構(gòu)選擇數(shù)據(jù)結(jié)構(gòu) 一維數(shù)組一維數(shù)組d d di di中存放從源點(diǎn)中存放從源點(diǎn)v0v0到到vivi的當(dāng)前最短路徑長度，該路徑的當(dāng)前最短路徑長度，該路徑上除頂點(diǎn)上除頂點(diǎn)vivi自身外，其余頂點(diǎn)都屬于自身外，其余頂點(diǎn)都屬于S S，并且是所有這些路，并且是所有這些路徑中的最短者。徑中的最短者。 一維整型數(shù)組一維整型數(shù)組pathpath pathi pathi給出從給出從v0v0到頂點(diǎn)到頂點(diǎn)vivi的最短路徑上，位于頂點(diǎn)的最短路徑上，位于頂點(diǎn)vivi前前面的那個頂點(diǎn)。面的那個頂點(diǎn)。例如：從例如：

23、從v0v0到到v1v1的最短路徑為的最短路徑為v0,v2,v3,v1v0,v2,v3,v1）則有則有path1=3path1=3，path3=2path3=2，path2=0path2=0一維布爾數(shù)組一維布爾數(shù)組s s 若若sisi為為truetrue，表示頂點(diǎn)，表示頂點(diǎn)vivi在在S S中；否則表示中；否則表示vivi在在V-SV-S中。中。Sd0path0d1path1d2path2d3path3d4path4d5path50 0，-1l 初始狀態(tài)初始狀態(tài)S=v0S=v0，T=T=其余頂點(diǎn)其余頂點(diǎn) 。0 02 24 41 170705 53 350501010353530303 31515

24、2020101015152020源點(diǎn)源點(diǎn)v0到自身的路徑長到自身的路徑長度為度為0，路徑上，路徑上0前面的前面的頂點(diǎn)不存在因此為頂點(diǎn)不存在因此為-1。初始狀態(tài)下初始狀態(tài)下T T中頂點(diǎn)中頂點(diǎn)vivi對應(yīng)的當(dāng)前最短路徑長度對應(yīng)的當(dāng)前最短路徑長度didi和該路徑和該路徑上上i i前面的結(jié)點(diǎn)前面的結(jié)點(diǎn)pathipathi值為：值為：若存在若存在，則，則didi為為弧上的權(quán)值弧上的權(quán)值w(v0,vi) w(v0,vi) ，且，且pathi=0pathi=0；若不存在若不存在 ，則，則didi為為，且，且pathi=-1pathi=-1。50，010，0，-170，0，-1第一條最短路徑是第一條最短路徑是

25、T=V-v0T=V-v0集合中所有頂點(diǎn)的當(dāng)前集合中所有頂點(diǎn)的當(dāng)前最短路徑中最短者：最短路徑中最短者： l 求第一條最短路徑求第一條最短路徑Sd0path0d1path1d2path2d3path3d4path4d5path50 0，-150，010，0，-170，0，-10 02 24 41 170705 53 350501010353530303 315152020101015152020選擇頂點(diǎn)選擇頂點(diǎn)v2v2加入集合加入集合S S，則，則d2d2為為源點(diǎn)源點(diǎn)v0v0到頂點(diǎn)到頂點(diǎn)v2v2的最短路徑，的最短路徑，path2path2為該最短路徑上頂點(diǎn)為該最短路徑上頂點(diǎn)v2v2前前面的那個頂點(diǎn)

26、面的那個頂點(diǎn)v0 v0 。0 min |- id kd ivVv0 02 24 41 170705 53 350501010353530303 315152020101015152020Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-1 min , ( , )d id i d kw k i更新更新dd和和pathpath若若di值被更新，則值被更新，則pathi值也隨之更新為值也隨之更新為k。l重復(fù)下面步驟：重復(fù)下面步驟：（1 1按照非減次序選擇下一條最短路徑的

27、終點(diǎn)按照非減次序選擇下一條最短路徑的終點(diǎn)T=V-ST=V-S中具有最短的當(dāng)前最短路徑長度的頂點(diǎn)中具有最短的當(dāng)前最短路徑長度的頂點(diǎn)vkvk），），滿足：滿足： min | d kd iiVSl直到直到SV時算法結(jié)束。時算法結(jié)束。（2） vk加入加入S集合中后，修正集合中后，修正T中剩余頂點(diǎn)中剩余頂點(diǎn)vi的當(dāng)前最短路徑長度的當(dāng)前最短路徑長度di和和pathi值：值：若若di更新，則更新，則pathi也相應(yīng)的更新為也相應(yīng)的更新為k min , ( , )d id i d kw k i0 02 24 41 170705 53 350501010353530303 3151520201010151520

28、20Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-1選擇頂點(diǎn)選擇頂點(diǎn)v3加入加入S。則。則d3為源點(diǎn)為源點(diǎn)v0到頂點(diǎn)到頂點(diǎn)v3的最短的最短路徑，路徑， path3為最短路徑為最短路徑上頂點(diǎn)上頂點(diǎn)v3前面的那個頂點(diǎn)。前面的那個頂點(diǎn)。0 02 24 41 170705 53 350501010353530303 315152020101015152020Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0

29、，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10 02 24 41 170705 53 350501010353530303 315152020101015152020Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-1將頂點(diǎn)將頂點(diǎn)v1加入加入S。則。則d1為為源點(diǎn)源點(diǎn)v0到頂點(diǎn)到頂點(diǎn)v1的最短路的最短路徑，徑，path1為最短

30、路徑上為最短路徑上頂點(diǎn)頂點(diǎn)v1前面的那個頂點(diǎn)。前面的那個頂點(diǎn)。0 02 24 41 170705 53 350501010353530303 315152020101015152020Sd0path0d1path1d2path2d3path3d4path4d5path5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-10 02 24 41 170705 53 350501010353530303 3151520201010

31、15152020Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-1選擇頂點(diǎn)選擇頂點(diǎn)v4加入加入S。則。則d4為源點(diǎn)為源點(diǎn)v0到頂點(diǎn)到頂點(diǎn)v4的最短的最短路徑，路徑， path4為最短路徑為最短路徑上頂點(diǎn)上頂點(diǎn)v4前面的那個頂點(diǎn)。前面的那個頂點(diǎn)。0 02 24 41 170705 53 350501010353530303 3151520201010

32、15152020Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-10,2,3,1,40，-145，310，025，255，1，-1Dijkstra算法算法(Dijkstra Algorithm) Dijkstra算法算法(Dijkstra Algorithm)是單源最短路徑問題是單源最短路徑問題的經(jīng)典解法之一，基本思想如下：的經(jīng)典解法之一，基本思想

33、如下：假定有一個待搜索的頂點(diǎn)表假定有一個待搜索的頂點(diǎn)表VL，初始化時做：，初始化時做： dist(s)0，dist(i)=(is)，VL=V。每次從。每次從VL非空非空集中選取這樣的一個頂點(diǎn)集中選取這樣的一個頂點(diǎn)u，它的，它的dist(u)最小。將選最小。將選出的出的u點(diǎn)作為搜索頂點(diǎn)，對于其它還在點(diǎn)作為搜索頂點(diǎn)，對于其它還在VL內(nèi)的頂點(diǎn)內(nèi)的頂點(diǎn)v，假設(shè)假設(shè)E,而且而且dist(u)+w(u,v)dist(v)，則更新，則更新dist(v)為為dist(u)+w(u,v)，同時從，同時從VL中將中將u刪除，直到刪除，直到VL 成為空集時算法終止。成為空集時算法終止。Dijkstra串行算法串行算法輸入：邊權(quán)鄰接矩陣輸入：邊權(quán)鄰接矩陣W約定頂點(diǎn)約定頂點(diǎn)i，j之間無邊連接時之間無邊連接時w(i,j)=，且，且w(i,i) = 0）、）、 待計算頂點(diǎn)的標(biāo)號待計算頂點(diǎn)的標(biāo)號s輸出：輸出：dist(0 : N-1)，其中，其中dist(i)表示頂點(diǎn)表示頂點(diǎn)s到頂點(diǎn)到頂點(diǎn)i的最短路徑的最短路徑(1iN)procedure D