并行算法的一般设计策略

并行算法的一般设计策略1第一页，共六十五页，2022年，8月28日第六章并行算法的一般设计策略6.1串行算法的直接并行化6.2从问题描述开始设计并行算法6.3借用已有算法求解新问题6.4串行算法的直接并行化补充实例:八皇后问题和单源最短路径问题2第二页，共六十五页，2022年，8月28日设计并行算法一般有3种方法：

（1）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；

（2）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；

（3）借助已有的并行算法求解新问题。3第三页，共六十五页，2022年，8月28日6.1串行算法的直接并行化方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；并非所有的串行算法都可以并行化；一个好的串行算法并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法；显著优点：无需考虑算法的稳定性、收敛性等复杂问题。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)；/*每个处理器确定总处理器个数*/

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结束*/}8第八页，共六十五页，2022年，8月28日枚举排序枚举排序是一种最简单的排序算法。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其小的数的个数，令其为k，a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]，a[3]…a[n]比较，记录比其小的数的个数，依此类推。时间复杂度为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日枚举排序的并行算法对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。11第十一页，共六十五页，2022年，8月28日枚举排序并行算法输入：无序数组a[1]…a[n]输出：有序数组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

步骤⑵的时间复杂度为O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时⑴中的通信复杂度为O（n2）；所以总的计算复杂度为O（n），总的通信复杂度为O（n2）。12第十二页，共六十五页，2022年，8月28日快速排序（QuickSort）快速排序（QuickSort）是一种最基本的排序算法基本思想：在当前无序区R[1,n]中取一个记录作为比较的“基准”，用此基准将当前的无序区R[1,n]划分成左右两个无序的子区R[1,i-1]和R[i,n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏情况下，划分的结果是一边有n-1个元素，而另一边有0个元素。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是Θ（n2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O（nlogn）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。

13第十三页，共六十五页，2022年，8月28日快速排序算法的串行实现SISD上的快排序算法输入：无序序列(Aq,…,Ar)输出：有序序列(Aq,…,Ar)ProcedureQUICKSORT（A,q,r）

Beginifq<rthenx=Aqs=q//s为计数器，表示比基准元素小或等于的元素个数

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的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。15第十五页，共六十五页，2022年，8月28日快速排序并行算法输入：无序数组data[1,n]，使用的处理器个数2m输出：有序数组data[1,n]Begin para_quicksort(data,1,n,m,0)End假设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从问题描述开始设计并行算法方法描述从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。评注挖掘问题的固有特性与并行的关系；设计全新的并行算法是一个挑战性和创造性的工作。18第十八页，共六十五页，2022年，8月28日串匹配问题串匹配（StringMatching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。19第十九页，共六十五页，2022年，8月28日串匹配问题串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（KeywordMatching）。所谓关键词匹配，是指给定一个长为n的文本串T[1，n]和长为m的模式串P[1，m]，找出文本串T中与模式串所有精确匹配的子串的起始位置。20第二十页，共六十五页，2022年，8月28日KMP串匹配算法KMP算法首先是由D.E.Knuth、J.H.Morris以及V.R.Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP串匹配算的基本思想是：对给出的的主串（文本串）T［1，n］与模式串P[1，m]，假设在模式匹配的进程中，执行T[i]和P[j]的匹配检查。若T[i]=P[j]，则继续检查T[i+1]和P[j+1]是否匹配。若T[i]≠P[j]，则文本串指针无需回溯，模式串指针回溯至失败函数处。21第二十一页，共六十五页，2022年，8月28日KMP算法22第二十二页，共六十五页，2022年，8月28日并行串匹配算法的设计思路设计的思路为：将长为n的文本串T均匀划分成互不重叠的p段，分布于处理器0到p-1中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为（最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同）。再将长为m的模式串P和模式串的失败函数newnext播送到各处理器中。各处理器使用改进的KMP算法并行地对局部文本段进行匹配，找到所有段内匹配位置。23第二十三页，共六十五页，2022年，8月28日并行串匹配算法的设计思路但是每个局部段（第p-1段除外）段尾m-1字符中的匹配位置必须跨段才能找到。一个简单易行的办法就是每个处理器（处理器p-1除外）将本局部段的段尾m-1个字符传送给下一处理器，下一处理器接收到前一处理器传来的字符串后，再接合本段的段首m-1个字符构成一长为2(m-1)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是这样做算法的通信量很大，必须采用改进通信的方法降低通信复杂度。24第二十四页，共六十五页，2022年，8月28日降低通信复杂度的设计思路①降低播送模式串和newnext函数的通信复杂度。利用串的周期性质，先对模式串P作预处理，获得其最小周期长度|U|、最小周期个数s及后缀长度|V|（P=UsV），只需播送U，s，|V|和部分newnext函数就可以了，从而大大减少了播送模式串和newnext函数的通信量。而且串的最小周期和next函数之间的关系存在着某种简单规律，使得能够设计出常数时间复杂度的串周期分析算法。25第二十五页，共六十五页，2022年，8月28日降低通信复杂度的设计思路②降低每个处理器（处理器p-1除外）将本局部文本段的段尾m-1个字符传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长前缀串，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这样就把通信量从传送模式串P的最长前缀串降低到传送一个整数，从而大大地降低了通信复杂度。26第二十六页，共六十五页，2022年，8月28日判断串周期性的见证函数定义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]=.根据WIT[j]函数可以区分串是周期的还是非周期的：

1）、对于所有的2≤j≤m/2，当且仅当WIT[j]≠0时，则串是非周期的；

2）、对于所有的2≤j≤m/2，若存在某个j，使得WIT[j]=0，则串是周期的；例：p1375.7假定P1=abaababa,P2=abaabaaab,P3=abaabaaabaabab,试计各自的WIT[j]函数，并判断他们的周期性27第二十七页，共六十五页，2022年，8月28日研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性。串可以分为周期的和非周期的。可以引入见证函数（WitnessFunction）来判断串的周期性。确定了串的周期性后就可以先研究非周期串的匹配，然后在此基础上再研究周期串的匹配。对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数。先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。

28第二十八页，共六十五页，2022年，8月28日假设T=abaababaababaababaababa，n=23，P=abaababa，m=8。由见证函数可知P是非周期串。因为P只可能在前16个位置上与T匹配，所以在找所有“可能位置”时只考虑T的前16个字符。匹配时，先要计算见证函数值，然后由其计算的值，找到可能匹配的位置。计算时，可以所有的块并行计算。先将P和T分成长度为2的块，用模式块(ab)与正文块(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)进行匹配可知模式块(ab)在位置1，4，6，9，11，14，16出现匹配。再把P与T划分成长度为4的块，用模式块(abaa)与正文块(abaa)(baba)(abab)(aaba)进行匹配可知在位置1，6，11，16出现匹配（位置4、9、14被淘汰）；最后用模式串(abaababa)在正文串的位置1，6，11，16进行检查，排除那些不匹配的位置。本例中这4个位置都匹配。

29第二十九页，共六十五页，2022年，8月28日6.3借用已有算法求解新问题方法描述找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。评注这是一项创造性的工作，两类问题表面上往往完全不同，因此很难联想到被借用的方法，需要设计者有敏锐的观察力和丰富的并行算法设计经验。欲使用借用法时，要注意观察问题的特征和算法的结构、形式，联想与本问题相似的已有算法。可以注意寻找要解决的问题与某些著名问题之间的相似性或本问题的算法与某些著名算法之间的相似性。使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。30第三十页，共六十五页，2022年，8月28日小结设计并行算法是一件复杂的事情，而并行算法的设计这门学科还属于发展中的一门学科，所以目前尚无一套普遍实用的、系统的设计方法学；本章介绍的三种并行程序设计方法显然不能涵盖并行程序设计的全部。算法设计是很灵活而无定规可循的。以上介绍的三种方法只是为并行算法设计提供了三条可以尝试的思路。31第三十一页，共六十五页，2022年，8月28日附1：八皇后问题所谓八皇后问题（EightQueensProblem），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后和，不允许或者

的情况出现。32第三十二页，共六十五页，2022年，8月28日八皇后问题的串行递归算法procedurePlaceQueens(chessboard,row)/*从chessboard的第row行开始放置皇后*/Beginifrow>8thenOutputResult(chessboard) /*结束递归并输出结果*/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 /*在当前位置放置一个皇后*/（4.2）go(step+1,place) /*递归地从下一行开始放置皇后*/ endif

endforendifEnd/*PlaceQueens*/33第三十三页，共六十五页，2022年，8月28日八皇后问题的并行算法该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上2个皇后，这样就可以产生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发送NewTask信号

(ⅱ)向从进程i发送一个新棋盘

else (ⅰ)向从进程i发送Terminate信号

(ⅱ)active_slaves=active_slaves-1 endifendwhileEnd/*EightQueensMaster*/35第三十五页，共六十五页，2022年，8月28日从进程算法procedureEightQueenSlaveBegin（1）向主进程发送Ready信号（2）finished=false（3）whilenotfinisheddo

（3.1）从主进程接收信号signal

（3.2）ifsignal=NewTaskthen (ⅰ)从主进程接收新棋盘

(ⅱ)if新棋盘合法then

在新棋盘的基础上找出所有合法的解，并将解发送给主进程

endifelse/*signal=Terminate*/finished=trueendif endwhileEnd/*EightQueenSlave*/36第三十六页，共六十五页，2022年，8月28日附2：单源最短路径问题单源最短路径(SingleSourceShortestPath)问题是指求从一个指定顶点s到其它所有顶点i之间的距离，因为是单一顶点到其它顶点的距离，所以称为单源。设图G(V,E)是一个有向加权网络，其中V和E分别为顶点集合和边集合，其边权邻接矩阵为W，边上权值w(i,j)>0，i,j∈V，V={0,1,…,N-1}。设dist(i)为最短的路径长度，即距离，其中s∈V且i≠s。这里采用著名的Dijkstra算法，并将其并行化。37第三十七页，共六十五页，2022年，8月28日最短路径问题用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图中的边是否有路可达另一顶点？若有多条路径可达，则在所经过的路径中，各边上权值之和最小的一条路径——最短路径。这就是路由选择。如：邮政自动分拣机的路选装置、计算机网络中的路由选择等。问题提出38第三十八页，共六十五页，2022年，8月28日单源最短路径：指的是对已知图G=(V,E)，给定源点s∈V，找出s到图中其它各顶点的最短路径。每对结点间的最短路径指的是对已知图G=(V,E)，任意的顶点Vi,Vj

∈V，找出从Vi到Vj的最短路径。两种最常见的最短路径算法：求单源最短路径的迪杰斯特拉（Djikstra）算法和求所有顶点之间的最短路径的弗洛伊德（Floyd）算法。39第三十九页，共六十五页，2022年，8月28日单源最短路径问题：给定带权有向图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)带权的有向图G(b)图G顶点0的单源最短路径迪杰斯特拉算法按从源点到其他各顶点的最短路径长度的从小到大的次序逐一产生最短路径。41第四十一页，共六十五页，2022年，8月28日

把V分成两组： （1）S：存放已求得最短路径的顶点的集合 （2）T=V-S：尚未确定最短路径的顶点集合 将T中顶点按最短路径非递减的次序加入到S中。迪杰斯特拉（Dijkstra）算法思想： 这个过程中，总保持：从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。而且每个顶点对应一个距离值：

S中顶点对应的距离值，是从V0到此顶点的最短路径长度；

T中顶点对应的距离值，是从V0到此顶点的只包括S中顶点作中间顶点的当前最短路径长度。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日迪杰斯特拉算法求单源最短路径步骤：首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。初始状态下集合S中只有源点v0，即：

S={v0}，T={其余顶点}。T中顶点vi对应的当前最短路径长度： 若存在<v0,vi>，为<v0,vi>弧上的权值w(v0,vi)

若不存在<v0,vi>，为∞49第四十九页，共六十五页，2022年，8月28日从T中选取一个当前最短路径长度最小的顶点vk加入S。对T中剩余顶点vi的当前最短路径长度进行修改： 若加进vk作中间顶点，从v0到vi的距离值比不加vk的路径要短，则修改此距离值。重复上述步骤，按照当前最短路径长度的非减次序产生下一条最短路径，并将该路径的终点tT加入S中，并更新T中剩余顶点的当前最短路径长度。直到S＝V时（即从源点v0到其他所有结点之间的最短路径都已求得为止），算法结束。50第五十页，共六十五页，2022年，8月28日选择数据结构

一维数组d

d[i]中存放从源点v0到vi的当前最短路径长度，该路径上除顶点vi自身外，其余顶点都属于S，并且是所有这些路径中的最短者。

一维整型数组path

path[i]给出从v0到顶点vi的最短路径上，位于顶点vi前面的那个顶点。 例如：从v0到v1的最短路径为（v0,v2,v3,v1） 则有path[1]=3，path[3]=2，path[2]=0一维布尔数组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

初始状态S={v0}，T={其余顶点}。024170535010353031520101520源点v0到自身的路径长度为0，路径上0前面的顶点不存在因此为-1。初始状态下T中顶点vi对应的当前最短路径长度d[i]和该路径上i前面的结点path[i]值为：若存在<v0,vi>，则d[i]为<v0,vi>弧上的权值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}集合中所有顶点的当前最短路径中最短者：

求第一条最短路径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[]和path[]若d[i]值被更新，则path[i]值也随之更新为k。0254第五十四页，共六十五页，2022年，8月28日重复下面步骤：（1）按照非减次序选择下一条最短路径的终点（T=V-S中具有最短的当前最短路径长度的顶点vk），满足：直到S＝V时算法结束。（2）vk加入S集合中后，修正T中剩余顶点vi的当前最短路径长度d[i]和path[i]值：若d[i]更新，则path[i]也相应的更新为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