并行算法的一般設(shè)計策略

并行算法的一般設(shè)計策略1第一頁，共六十五頁，2022年，8月28日第六章并行算法的一般設(shè)計策略6.1串行算法的直接并行化6.2從問題描述開始設(shè)計并行算法6.3借用已有算法求解新問題6.4串行算法的直接并行化補充實例:八皇后問題和單源最短路徑問題2第二頁，共六十五頁，2022年，8月28日設(shè)計并行算法一般有3種方法：

（1）檢查和開拓現(xiàn)有串行算法中固有的并行性，直接將其并行化，該方法并不是對所有問題總是可行的，但對很多應(yīng)用問題仍不失為一種有效的方法；

（2）從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從頭設(shè)計一個全新的并行算法，這種方法有一定難度，但所設(shè)計的并行算法通常是高效的；

（3）借助已有的并行算法求解新問題。3第三頁，共六十五頁，2022年，8月28日6.1串行算法的直接并行化方法描述發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。評注由串行算法直接并行化的方法是并行算法設(shè)計的最常用方法之一；并非所有的串行算法都可以并行化；一個好的串行算法并不能并行化為一個好的并行算法，相反一個不好的串行算法則有可能產(chǎn)生很優(yōu)秀的并行算法，例如枚舉排序不是一種好的串行算法。但是將其直接并行化后可以得到比較好的并行算法；顯著優(yōu)點：無需考慮算法的穩(wěn)定性、收斂性等復(fù)雜問題。4第四頁，共六十五頁，2022年，8月28日積分算法的直接并行化--π的計算5第五頁，共六十五頁，2022年，8月28日計算π的串行C代碼#defineN1000000main(){ doublelocal,pi=0.0,w; longi; w=1.0/N; for(i=0;i<N;i++){ local=(i+0.5)*w; pi=pi+4.0/(1.0+local*local); } printf(“piis%f\n”,pi*w);}6第六頁，共六十五頁，2022年，8月28日k個處理器并行地計算部分和7第七頁，共六十五頁，2022年，8月28日計算π的MPI代碼#defineN100000main(){doublelocal=0.0，pi，w，temp=0.0；longi，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)；/*每個處理器確定總處理器個數(shù)*/

B：for(i=taskid；i<N；i=i+numtask){temp=(i+0.5)*w；local=4.0/(1.0+temp*temp)+local；}C：MPI_Reduce(&local,&pi,1,MPI_Double,MPI_SUM,0,MPI_COMM_WORLD)；/*MPI歸約操作*/D：if(taskid==0)printf(“piis%f\n”，pi*w)；MPI_Finalize()；/*MPI結(jié)束*/}8第八頁，共六十五頁，2022年，8月28日枚舉排序枚舉排序是一種最簡單的排序算法。該算法的具體思想是（假設(shè)按關(guān)鍵字遞增排序），對每一個待排序的元素統(tǒng)計小于它的所有元素的個數(shù)，從而得到該元素最終處于序列中的位置。假定待排序的n個數(shù)存在a[1]…a[n]中。首先將a[1]與a[2]…a[n]比較，記錄比其小的數(shù)的個數(shù)，令其為k，a[1]就被存入有序的數(shù)組b[1]…b[n]的b[k+1]位置上；然后將a[2]與a[1]，a[3]…a[n]比較，記錄比其小的數(shù)的個數(shù)，依此類推。時間復(fù)雜度為O（n2）。9第九頁，共六十五頁，2022年，8月28日枚舉排序串行算法輸入：a[1]…a[n]輸出：b[1]…b[n]Beginfori=1tondo(1) k=1(2) forj=1tondo ifa[i]>a[j]then

k=k+1 endif endfor(3) b[k]=a[i]endforEnd10第十頁，共六十五頁，2022年，8月28日枚舉排序的并行算法對該算法的并行化是很簡單的，假設(shè)對一個長為n的輸入序列使用n個處理器進行排序，只需每個處理器負責(zé)完成對其中一個元素的定位，然后將所有的定位信息集中到主進程中，由主進程負責(zé)完成所有元素的最終排位。11第十一頁，共六十五頁，2022年，8月28日枚舉排序并行算法輸入：無序數(shù)組a[1]…a[n]輸出：有序數(shù)組b[1]…b[n]Begin(1) P0播送a[1]…a[n]給所有Pi(2) forallPiwhere1≤i≤npara-do(2.1)k=1(2.2)forj=1tondo if(a[i]>a[j])or(a[i]=a[j]andi>j)then

k=k+1 endif endfor(3) P0收集k并按序定位End

步驟⑵的時間復(fù)雜度為O（n）；步驟⑶中主進程完成的數(shù)組元素重定位操作的時間復(fù)雜度為O（n），通信復(fù)雜度分別為O（n）；同時⑴中的通信復(fù)雜度為O（n2）；所以總的計算復(fù)雜度為O（n），總的通信復(fù)雜度為O（n2）。12第十二頁，共六十五頁，2022年，8月28日快速排序（QuickSort）快速排序（QuickSort）是一種最基本的排序算法基本思想：在當(dāng)前無序區(qū)R[1,n]中取一個記錄作為比較的“基準”，用此基準將當(dāng)前的無序區(qū)R[1,n]劃分成左右兩個無序的子區(qū)R[1,i-1]和R[i,n](1≤i≤n)，且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準的關(guān)鍵字，右邊的無序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準的關(guān)鍵字?？焖倥判蛩惴ǖ男阅苤饕獩Q定于輸入數(shù)組的劃分是否均衡，而這與基準元素的選擇密切相關(guān)。在最壞情況下，劃分的結(jié)果是一邊有n-1個元素，而另一邊有0個元素。如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個算法的復(fù)雜度將是Θ（n2）。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為O（nlogn）。在一般的情況下該算法仍能保持O（nlogn）的復(fù)雜度，只不過其具有更高的常數(shù)因子。

13第十三頁，共六十五頁，2022年，8月28日快速排序算法的串行實現(xiàn)SISD上的快排序算法輸入：無序序列(Aq,…,Ar)輸出：有序序列(Aq,…,Ar)ProcedureQUICKSORT（A,q,r）

Beginifq<rthenx=Aqs=q//s為計數(shù)器，表示比基準元素小或等于的元素個數(shù)

fori=q+1tordoifAi≤xthens=s+1swap(As,Ai)endifswap(Aq,As)

QUICKSORT(A,q,s)

QUICKSORT(A,s+1,r)endifEnd14第十四頁，共六十五頁，2022年，8月28日快速排序算法的并行思路快速排序算法并行化的一個簡單思想是，對每次劃分過后所得到的兩個序列分別使用兩個處理器完成遞歸排序。例如對一個長為n的序列，首先劃分得到兩個長為n/2的序列，將其交給兩個處理器分別處理；而后進一步劃分得到四個長為n/4的序列，再分別交給四個處理器處理；如此遞歸下去最終得到排序好的序列。當(dāng)然這里舉的是理想的劃分情況，如果劃分步驟不能達到平均分配的目的，那么排序的效率會相對較差。15第十五頁，共六十五頁，2022年，8月28日快速排序并行算法輸入：無序數(shù)組data[1,n]，使用的處理器個數(shù)2m輸出：有序數(shù)組data[1,n]Begin para_quicksort(data,1,n,m,0)End假設(shè)quicksort(data,i,j)表示快速排序串行算法16第十六頁，共六十五頁，2022年，8月28日快速排序并行算法procedurepara_quicksort(data,i,j,m,id)Begin(1) ifm=0then (1.1) Pidcallquicksort(data,i,j)else(1.2) Pid:r=patrition(data,i,j)(1.3) Pidsenddata[r+1,j]toPid+2m-1(1.4) para_quicksort(data,i,r-1,m-1,id)(1.5) para_quicksort(data,r+1,j,m-1,id+2m-1)(1.6) Pid+2m-1senddata[r+1,j]backtoPid endifEnd17第十七頁，共六十五頁，2022年，8月28日

6.2從問題描述開始設(shè)計并行算法方法描述從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計一個全新的并行算法。評注挖掘問題的固有特性與并行的關(guān)系；設(shè)計全新的并行算法是一個挑戰(zhàn)性和創(chuàng)造性的工作。18第十八頁，共六十五頁，2022年，8月28日串匹配問題串匹配（StringMatching）問題是計算機科學(xué)中的一個基本問題，也是復(fù)雜性理論中研究的最廣泛的問題之一。它在文字編輯處理、圖像處理、文獻檢索、自然語言識別、生物學(xué)等領(lǐng)域有著廣泛的應(yīng)用。而且，串匹配是這些應(yīng)用中最耗時的核心問題，好的串匹配算法能顯著地提高應(yīng)用的效率。因此，研究并設(shè)計快速的串匹配算法具有重要的理論價值和實際意義。19第十九頁，共六十五頁，2022年，8月28日串匹配問題串匹配問題實際上就是一種模式匹配問題，即在給定的文本串中找出與模式串匹配的子串的起始位置。最基本的串匹配問題是關(guān)鍵詞匹配（KeywordMatching）。所謂關(guān)鍵詞匹配，是指給定一個長為n的文本串T[1，n]和長為m的模式串P[1，m]，找出文本串T中與模式串所有精確匹配的子串的起始位置。20第二十頁，共六十五頁，2022年，8月28日KMP串匹配算法KMP算法首先是由D.E.Knuth、J.H.Morris以及V.R.Pratt分別設(shè)計出來的，所以該算法被命名為KMP算法。KMP串匹配算的基本思想是：對給出的的主串（文本串）T［1，n］與模式串P[1，m]，假設(shè)在模式匹配的進程中，執(zhí)行T[i]和P[j]的匹配檢查。若T[i]=P[j]，則繼續(xù)檢查T[i+1]和P[j+1]是否匹配。若T[i]≠P[j]，則文本串指針無需回溯，模式串指針回溯至失敗函數(shù)處。21第二十一頁，共六十五頁，2022年，8月28日KMP算法22第二十二頁，共六十五頁，2022年，8月28日并行串匹配算法的設(shè)計思路設(shè)計的思路為：將長為n的文本串T均勻劃分成互不重疊的p段，分布于處理器0到p-1中，且使得相鄰的文本段分布在相鄰的處理器中，顯然每個處理器中局部文本段的長度為（最后一個處理器可在其段尾補上其它特殊字符使其長度與其它相同）。再將長為m的模式串P和模式串的失敗函數(shù)newnext播送到各處理器中。各處理器使用改進的KMP算法并行地對局部文本段進行匹配，找到所有段內(nèi)匹配位置。23第二十三頁，共六十五頁，2022年，8月28日并行串匹配算法的設(shè)計思路但是每個局部段（第p-1段除外）段尾m-1字符中的匹配位置必須跨段才能找到。一個簡單易行的辦法就是每個處理器（處理器p-1除外）將本局部段的段尾m-1個字符傳送給下一處理器，下一處理器接收到前一處理器傳來的字符串后，再接合本段的段首m-1個字符構(gòu)成一長為2(m-1)的段間字符串，對此字符串做匹配，就能找到所有段間匹配位置。但是這樣做算法的通信量很大，必須采用改進通信的方法降低通信復(fù)雜度。24第二十四頁，共六十五頁，2022年，8月28日降低通信復(fù)雜度的設(shè)計思路①降低播送模式串和newnext函數(shù)的通信復(fù)雜度。利用串的周期性質(zhì)，先對模式串P作預(yù)處理，獲得其最小周期長度|U|、最小周期個數(shù)s及后綴長度|V|（P=UsV），只需播送U，s，|V|和部分newnext函數(shù)就可以了，從而大大減少了播送模式串和newnext函數(shù)的通信量。而且串的最小周期和next函數(shù)之間的關(guān)系存在著某種簡單規(guī)律，使得能夠設(shè)計出常數(shù)時間復(fù)雜度的串周期分析算法。25第二十五頁，共六十五頁，2022年，8月28日降低通信復(fù)雜度的設(shè)計思路②降低每個處理器（處理器p-1除外）將本局部文本段的段尾m-1個字符傳送給下一處理器的通信復(fù)雜度。每個處理器在其段尾m-1個字符中找到模式串P的最長前綴串，因為每個處理器上都有模式串信息，所以只需傳送該最長前綴串的長度就行了。這樣就把通信量從傳送模式串P的最長前綴串降低到傳送一個整數(shù)，從而大大地降低了通信復(fù)雜度。26第二十六頁，共六十五頁，2022年，8月28日判斷串周期性的見證函數(shù)定義5.4對于給定的j(1≤j≤m/2)，如果P[j:m]≠P[1:m-j+1]，則存在某個（1≤≤m-j+1），使得P()≠P(s)，其中s=j-1+，記WIT[j]=.根據(jù)WIT[j]函數(shù)可以區(qū)分串是周期的還是非周期的：

1）、對于所有的2≤j≤m/2，當(dāng)且僅當(dāng)WIT[j]≠0時，則串是非周期的；

2）、對于所有的2≤j≤m/2，若存在某個j，使得WIT[j]=0，則串是周期的；例：p1375.7假定P1=abaababa,P2=abaabaaab,P3=abaabaaabaabab,試計各自的WIT[j]函數(shù)，并判斷他們的周期性27第二十七頁，共六十五頁，2022年，8月28日研究發(fā)現(xiàn)，兩串能否匹配是與串本身的特性有關(guān)的。這種特性，就是串的周期性。串可以分為周期的和非周期的?？梢砸胍娮C函數(shù)（WitnessFunction）來判斷串的周期性。確定了串的周期性后就可以先研究非周期串的匹配，然后在此基礎(chǔ)上再研究周期串的匹配。對于非周期串的研究，就是如何利用見證函數(shù)快速地找出P在T中的位置。為此，引入競爭函數(shù)。先把正文串分成小段，借助于見證函數(shù)并行地計算競爭函數(shù)值，找出那些可能匹配的位置。然后逐步擴大正文串分段的長度，并計算競爭函數(shù)值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中驗證哪些是符合要求的位置。

28第二十八頁，共六十五頁，2022年，8月28日假設(shè)T=abaababaababaababaababa，n=23，P=abaababa，m=8。由見證函數(shù)可知P是非周期串。因為P只可能在前16個位置上與T匹配，所以在找所有“可能位置”時只考慮T的前16個字符。匹配時，先要計算見證函數(shù)值，然后由其計算的值，找到可能匹配的位置。計算時，可以所有的塊并行計算。先將P和T分成長度為2的塊，用模式塊(ab)與正文塊(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)進行匹配可知模式塊(ab)在位置1，4，6，9，11，14，16出現(xiàn)匹配。再把P與T劃分成長度為4的塊，用模式塊(abaa)與正文塊(abaa)(baba)(abab)(aaba)進行匹配可知在位置1，6，11，16出現(xiàn)匹配（位置4、9、14被淘汰）；最后用模式串(abaababa)在正文串的位置1，6，11，16進行檢查，排除那些不匹配的位置。本例中這4個位置都匹配。

29第二十九頁，共六十五頁，2022年，8月28日6.3借用已有算法求解新問題方法描述找出求解問題和某個已解決問題之間的聯(lián)系；改造或利用已知算法應(yīng)用到求解問題上。評注這是一項創(chuàng)造性的工作，兩類問題表面上往往完全不同，因此很難聯(lián)想到被借用的方法，需要設(shè)計者有敏銳的觀察力和豐富的并行算法設(shè)計經(jīng)驗。欲使用借用法時，要注意觀察問題的特征和算法的結(jié)構(gòu)、形式，聯(lián)想與本問題相似的已有算法?？梢宰⒁鈱ふ乙鉀Q的問題與某些著名問題之間的相似性或本問題的算法與某些著名算法之間的相似性。使用矩陣乘法算法求解所有點對間最短路徑是一個很好的范例。30第三十頁，共六十五頁，2022年，8月28日小結(jié)設(shè)計并行算法是一件復(fù)雜的事情，而并行算法的設(shè)計這門學(xué)科還屬于發(fā)展中的一門學(xué)科，所以目前尚無一套普遍實用的、系統(tǒng)的設(shè)計方法學(xué)；本章介紹的三種并行程序設(shè)計方法顯然不能涵蓋并行程序設(shè)計的全部。算法設(shè)計是很靈活而無定規(guī)可循的。以上介紹的三種方法只是為并行算法設(shè)計提供了三條可以嘗試的思路。31第三十一頁，共六十五頁，2022年，8月28日附1：八皇后問題所謂八皇后問題（EightQueensProblem），是在8*8格的棋盤上，放置8個皇后。要求每行每列放一個皇后,而且每一條對角線和每一條反對角線上最多只能有一個皇后，即對同時放置在棋盤的任意兩個皇后和，不允許或者

的情況出現(xiàn)。32第三十二頁，共六十五頁，2022年，8月28日八皇后問題的串行遞歸算法procedurePlaceQueens(chessboard,row)/*從chessboard的第row行開始放置皇后*/Beginifrow>8thenOutputResult(chessboard) /*結(jié)束遞歸并輸出結(jié)果*/else

forcol=1to8do /*判斷是否有列、對角線或反對角線沖突*/（1）no_collision=true（2）i=1（3）whileno_collisionandi<rowdo（3.1）ifcollides(i,chessboard[i],row,col)thenno_collision=falseendif

（3.2）i=i+1endwhile

（4）ifno_collisionthen

（4.1）chessboard[row]=col /*在當(dāng)前位置放置一個皇后*/（4.2）go(step+1,place) /*遞歸地從下一行開始放置皇后*/ endif

endforendifEnd/*PlaceQueens*/33第三十三頁，共六十五頁，2022年，8月28日八皇后問題的并行算法該算法是將八皇后所有可能的解置于相應(yīng)的棋盤上，主進程負責(zé)生成初始化的棋盤，并將該棋盤發(fā)送到某個空閑的從進程，由該從進程求出該棋盤上滿足初始化條件的所有的解。這里，我們假定主進程只初始化棋盤的前兩列，即在棋盤的前兩列分別放上2個皇后，這樣就可以產(chǎn)生8*8=64個棋盤。34第三十四頁，共六十五頁，2022年，8月28日主進程算法procedureEightQueensMasterBegin（1）active_slaves=n//活動從進程（2）whileactive_slaves>0do

（2.1）從某個從進程i接收信號signal

（2.2）ifsignal=Accomplishedthen

從從進程i接收并記錄解

endif

（2.3）ifhas_more_boardsthen (ⅰ)向從進程i發(fā)送NewTask信號

(ⅱ)向從進程i發(fā)送一個新棋盤

else (ⅰ)向從進程i發(fā)送Terminate信號

(ⅱ)active_slaves=active_slaves-1 endifendwhileEnd/*EightQueensMaster*/35第三十五頁，共六十五頁，2022年，8月28日從進程算法procedureEightQueenSlaveBegin（1）向主進程發(fā)送Ready信號（2）finished=false（3）whilenotfinisheddo

（3.1）從主進程接收信號signal

（3.2）ifsignal=NewTaskthen (ⅰ)從主進程接收新棋盤

(ⅱ)if新棋盤合法then

在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送給主進程

endifelse/*signal=Terminate*/finished=trueendif endwhileEnd/*EightQueenSlave*/36第三十六頁，共六十五頁，2022年，8月28日附2：單源最短路徑問題單源最短路徑(SingleSourceShortestPath)問題是指求從一個指定頂點s到其它所有頂點i之間的距離，因為是單一頂點到其它頂點的距離，所以稱為單源。設(shè)圖G(V,E)是一個有向加權(quán)網(wǎng)絡(luò)，其中V和E分別為頂點集合和邊集合，其邊權(quán)鄰接矩陣為W，邊上權(quán)值w(i,j)>0，i,j∈V，V={0,1,…,N-1}。設(shè)dist(i)為最短的路徑長度，即距離，其中s∈V且i≠s。這里采用著名的Dijkstra算法，并將其并行化。37第三十七頁，共六十五頁，2022年，8月28日最短路徑問題用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖中的邊是否有路可達另一頂點？若有多條路徑可達，則在所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑。這就是路由選擇。如：郵政自動分揀機的路選裝置、計算機網(wǎng)絡(luò)中的路由選擇等。問題提出38第三十八頁，共六十五頁，2022年，8月28日單源最短路徑：指的是對已知圖G=(V,E)，給定源點s∈V，找出s到圖中其它各頂點的最短路徑。每對結(jié)點間的最短路徑指的是對已知圖G=(V,E)，任意的頂點Vi,Vj

∈V，找出從Vi到Vj的最短路徑。兩種最常見的最短路徑算法：求單源最短路徑的迪杰斯特拉（Djikstra）算法和求所有頂點之間的最短路徑的弗洛伊德（Floyd）算法。39第三十九頁，共六十五頁，2022年，8月28日單源最短路徑問題：給定帶權(quán)有向圖G=(V,E)，求從某個給定的源點v0V到其余各頂點的最短路徑。迪杰斯特拉算法

40第四十頁，共六十五頁，2022年，8月28日024170535010353031520101520源點終點最短路徑路徑長度01（0,2,3,1）452（0,2）103（0,2,3）254（0,2,3,1,4）555－∞(a)帶權(quán)的有向圖G(b)圖G頂點0的單源最短路徑迪杰斯特拉算法按從源點到其他各頂點的最短路徑長度的從小到大的次序逐一產(chǎn)生最短路徑。41第四十一頁，共六十五頁，2022年，8月28日

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

S中頂點對應(yīng)的距離值，是從V0到此頂點的最短路徑長度；

T中頂點對應(yīng)的距離值，是從V0到此頂點的只包括S中頂點作中間頂點的當(dāng)前最短路徑長度。42第四十二頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑1002417053501035303152010152050∞∞7043第四十三頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520105025∞7044第四十四頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞6045第四十五頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞5546第四十六頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞5547第四十七頁，共六十五頁，2022年，8月28日單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞5548第四十八頁，共六十五頁，2022年，8月28日迪杰斯特拉算法求單源最短路徑步驟：首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有頂點之間的最短路徑都已求得為止。初始狀態(tài)下集合S中只有源點v0，即：

S={v0}，T={其余頂點}。T中頂點vi對應(yīng)的當(dāng)前最短路徑長度： 若存在<v0,vi>，為<v0,vi>弧上的權(quán)值w(v0,vi)

若不存在<v0,vi>，為∞49第四十九頁，共六十五頁，2022年，8月28日從T中選取一個當(dāng)前最短路徑長度最小的頂點vk加入S。對T中剩余頂點vi的當(dāng)前最短路徑長度進行修改： 若加進vk作中間頂點，從v0到vi的距離值比不加vk的路徑要短，則修改此距離值。重復(fù)上述步驟，按照當(dāng)前最短路徑長度的非減次序產(chǎn)生下一條最短路徑，并將該路徑的終點tT加入S中，并更新T中剩余頂點的當(dāng)前最短路徑長度。直到S＝V時（即從源點v0到其他所有結(jié)點之間的最短路徑都已求得為止），算法結(jié)束。50第五十頁，共六十五頁，2022年，8月28日選擇數(shù)據(jù)結(jié)構(gòu)

一維數(shù)組d

d[i]中存放從源點v0到vi的當(dāng)前最短路徑長度，該路徑上除頂點vi自身外，其余頂點都屬于S，并且是所有這些路徑中的最短者。

一維整型數(shù)組path

path[i]給出從v0到頂點vi的最短路徑上，位于頂點vi前面的那個頂點。 例如：從v0到v1的最短路徑為（v0,v2,v3,v1） 則有path[1]=3，path[3]=2，path[2]=0一維布爾數(shù)組s

若s[i]為true，表示頂點vi在S中；否則表示vi在V-S中。

51第五十一頁，共六十五頁，2022年，8月28日Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-1

初始狀態(tài)S={v0}，T={其余頂點}。024170535010353031520101520源點v0到自身的路徑長度為0，路徑上0前面的頂點不存在因此為-1。初始狀態(tài)下T中頂點vi對應(yīng)的當(dāng)前最短路徑長度d[i]和該路徑上i前面的結(jié)點path[i]值為：若存在<v0,vi>，則d[i]為<v0,vi>弧上的權(quán)值w(v0,vi)

，且path[i]=0；若不存在<v0,vi>，則d[i]為∞，且path[i]=-1。50，010，0∞，-170，0∞，-1052第五十二頁，共六十五頁，2022年，8月28日第一條最短路徑是T=V-{v0}集合中所有頂點的當(dāng)前最短路徑中最短者：

求第一條最短路徑Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1024170535010353031520101520選擇頂點v2加入集合S，則d[2]為源點v0到頂點v2的最短路徑，path[2]為該最短路徑上頂點v2前面的那個頂點v0

。0253第五十三頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1頂點vk加入S后，對所有T=V-S集合中的剩余頂點vi

，按公式修正從源點v0到該頂點的當(dāng)前最短路徑長度：更新d[]和path[]若d[i]值被更新，則path[i]值也隨之更新為k。0254第五十四頁，共六十五頁，2022年，8月28日重復(fù)下面步驟：（1）按照非減次序選擇下一條最短路徑的終點（T=V-S中具有最短的當(dāng)前最短路徑長度的頂點vk），滿足：直到S＝V時算法結(jié)束。（2）vk加入S集合中后，修正T中剩余頂點vi的當(dāng)前最短路徑長度d[i]和path[i]值：若d[i]更新，則path[i]也相應(yīng)的更新為k55第五十五頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1選擇頂點v3加入S。則d[3]為源點v0到頂點v3的最短路徑，path[3]為最短路徑上頂點v3前面的那個頂點。02356第五十六頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-102357第五十七頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-10231將頂點v1加入S。則d[1]為源點v0到頂點v1的最短路徑，path[1]為最短路徑上頂點v1前面的那個頂點。58第五十八頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1{0,2,3,1}0，-145，310，025，255，1∞，-1023159第五十九頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1{0,2,3,1}0，-145，310，025，255，1∞，-10231選擇頂點v4加入S。則d[4]為源點v0到頂點v4的最短路徑，path[4]為最短路徑上頂點v4前面的那個頂點。460第六十頁，共六十五頁，2022年，8月28日024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010