软件设计师 http://www.educity.cn/jiaocheng/zg7.html
选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有的蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 需要注意的是：
（1）若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
（2）从源点s到终点v的最短路径简称为v的最短路径；从s到v的最短路径长度简称为v的最短距离，并记为SD（v）。
根据按长度递增的次序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
源点，红点1,红点2,……，红点n,蓝点k 距离为：
源点到红点n最短距离 + <红点n,蓝点k>的边长。
为求解方便，可设置一个向量D[0…n–1],对于每个蓝点v∈V–S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点（若有中间点，则必为红点）的\最短\路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V–S},则D[k]=SD（k）。
初始时，每个蓝点v的D[c]值应为权w
将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j,若k由蓝变红后使D[j]变小，则必定是由于
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
存在一条从s到j且包含新红点k的更短路径P=
对图中每对顶点u和v,找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。
但更常用的是弗洛伊德（Folyd）提出的求每一对顶点之间的最短路径的算法。设G=（V,E）是有n个顶点的有向图，顶点集合V={0,1,…，n–1}.图用邻接矩阵M表示。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2,…，Cn,其中C0是已知的带权邻接矩阵a,Ck（i,j）（0≤i,j 设在第k次递推之前已求得Ck-1（i,j）（0≤i,j （1）如果从顶点i到顶点j的最短路径不经过顶点k,则由Ck（i,j）定义知，从i到j中间的顶点序号不大于k的最短路径长度还是Ck-1（i,j）即Ck（i,j）=Ck-1（i,j）。 （2）如果从顶点i到顶点j的最短路径要经过顶点k,则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于Ck-1（i,k）和Ck-1（k,j）分别表示i到k和从k到j的中间顶点序号不大于k-1的最短路径长度，若Ck-1（i,k）+Ck-1（k,j） 软件设计师 http://www.educity.cn/jiaocheng/zg7.html Ck-1（i,k）+Ck-1（k,j）必定是i到j的中间顶点序号不大于是k的最短路径的长度，则Ck（i,j）=Ck-1（i,k）+Ck-1（k,j）。 1.3.4 拓扑排序 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v,若 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的； 若图中存在有向环，则不可能使顶点满足拓扑次序； 一个有向无环图可能有多个拓扑序列； 当有向图中存在有向环时，拓扑序列不存在。 一个大工程有许多项目组，有些项目的实行则存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用表活动网络，简称AOV网络，如图1-13所示。 对AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得在AOV网络中存在一条弧（i,j），则活动i排在活动j之前。例如对图1-35中的有向图的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567,02143657, 01243567等。 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 1.3.5 关键路径 在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如图1-14表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点，分别表示事件1~7,其中1表示工程开始状态，7表示工程结束状态，边上的权表示完成该活动所需的时间。 因AOE网络中的某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径（临界路径），关键路径上的活动为关键活动。 为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量。 Ve（j）、Vl（j） :顶点j事件最早、最迟发生时间。 e（i）、l（i）： 活动i最早、最迟开始时间。 从源点V1到某顶点Vj的最长路径长度，称为事件Vj的最早发生时间，记为Ve（j）。Ve（j）也是以Vj为起点的出边 求顶点Vj的Ve（j）和Vl（j）可按以下两步来做。 软件设计师 http://www.educity.cn/jiaocheng/zg7.html ①由源点开始向汇点递推 其中，E1是网络中以Vj为终点的入边集合。 ②由汇点开始向源点递推 其中，E2是网络中以Vj为起点的出边集合。 要求一个AOE的关键路径，一般需要根据以上变量列出一张表格，逐个检查。例如求图1-14所示的AOE关键路径的过程如表1-1所示。 表1-1 求关键路径的过程 因此，图1-14的关键活动为a1,a2,a4,a8和a9（即表1-1阴影所示活动），其对应的关键路径有两条，分别为（V1,V2, V5,V7）和（V1,V4,V5,V7），长度都是10。