4.π(6)=minπ(i)=7, r(4)=8, 5.r(4)=minπ(i)=8。 为了得到具体的路径走向，可以增设-个n维向量Q.初值均为1；然后将步骤c改 为： c.对全部i∈S门， 若π(i)>π(》十wn, 则π(i)←x()十w,Q(i)←j, 转b。 这样，Q()中存放的是最短路P()中，的直接前趋的结点号。比如上例运算结束时Q中 的值是 1515 312 例如从中可查，Q(6)=2,Q(2)=6,Q(5)=,Q(3)=,因此最后可以得到1到5的 最短道路是(1,35，v26)。 Dijkstra算法的正确性前面已经论述，以下讨论其计算复杂度。 算法的基本步骤是b和c。b所需要的比较次数取决于所采用的数据结构。如果S使 用特征向量中存储，使 1,若i∈S。 中(i)= 0,其它。 那么在b的选代需要3次比较，总比较次数是号(m-1), 如果采用邻接表的形式表示图G,由于每个结点的直接后继顺序可查，那么步骤c最 多褐要m(=空d)次加法和比较，这样D时k算法的计算复杂性是O(m)+O), 2.6.2边权为1时1到各点的最短路 在有些情况下，图(G所有的边权都相同。这时可以对Dijkstra算法进行改进，从而计 算到其余各点的最短路径。 算法描述如下： a.置x(1)=0,π(i)=∞，≥2， k=0,S=(1},Sg=1}。 b.第k步 置S1=「时∩S, r(i)=k+1,i∈SA+1, S=SUS+1。 c.若|S=|V(C)i,结束；否则一k+1,转b。 当算法进行第k次送代时，已经有S={i{π()=兔}以及S={π()≤}。此外S+ 表示结点集S中所有结点的直接后继集合。 ·26·
例2.6.2使用本算法求图2.24中1到其余各点的最短路径过程如下： 8.x(1)=0,π()=0， i=2,3,4,5,5,5=1}, b.k=0,w={1},51={2,3. π(2)=π(3)=15={1,2,3；， c.k=152={4,5,6}, π(4)=x(5)=π(6)=2.S=V(G)。 d.end. 定理2.6.1如果图C是以正向表或邻接表的数据结构表示，则本算法的计算复杂 性是O(m), 2.6.3边权任意时1到各点的最短路 当存在负权边时，情况会变得复杂…些。对··条权为 ,的边(，，)来说，因为从，到，的最短路可能经过， 假定，<0，在G一e,中很可能π()<π(i).例如在某个图 C中w,=一2，而G一e,有(i)=8,π()=7，就符合这种 情况。如果仍然采用Dijkstra算法，则π(j)至少为？，而不 是最多为6。因此，在有负权边时，Dijkstra算法可能失效。 Ford给出的算法解决了这一问题.现描述如下。 a.置π(1)=0，r(i)=o∞， i=2,3,n, 2 b.i从2到n,令 图2.21 π(t)←-min[π(i),min(π(j)+ww)], c.若全部π()都没变化，结束：否则转。 在算法的每一步，()都是从到，的最短路径长度的.上界。由于不存在负长回路， 因此u:到：的最短路长度是π()的下界。 由于云()在减小而且有下界，所以算法收敛同时存在极限。以下证明该极值确是从 ,到，的最短路长度。设算法结束时，对某个结点飞，有π(s),假定它经过的路径是(1,4， 1,…,52,1,5),显然有 π(s)=w(1,5）十w(,5:)十…十w(s), 对从：到，的另一条路径，比如μ=(1，-1…，，s),由于步豫6的等式成立，所以有 r(s一x(t:)≤e(1,5), π(t:)一r(1e)≤0(t,t). π(t）-π(1)≤(1，ts), 即π(s)≤w(μ)=w(们，t)十(t,th!)+…十w(1:5)。 因此π(x)是从1到巴，的最短路长。算法的正确性得证。以下讨论计算复杂性。 如果采用逆向表结构，步骤h需要进行m次加法和比较，现在分标c,即b要迭代的 ·27·
次数。假定没有负回路，则从1到任何其它结点的最短路径不会超过一1条边，因此经 过一1次迭代之后π()将保持不变。当然如果在第n次迭代时它仍在发生变化·只能说 明存在负长回路。因此有 定理2.6.2在最坏情况下Ford算法的计算复杂性是O(mn), 例2.6.3使用Ford算法求图2.25中8到其它各点最短路的过程如下： a.π(1)=0，π(2)=π(3)=π(4)。 六r(5)t(6)二0。 b.π(2)=7，π(3)=8，x(4)=11. x(5)=8,π(6)…。 c.π(2)=7，π(3)=6，x(4)=10, r(5)=8,r(6)=8。 d.π(2)=7，x(3)=6,x(1)=10, r(5)=8,π(6)=8。 图2.25 由于Ford算法主要取决于步骤b的迭代次数，因此 G中结点被检查的次序对算法收敛的快慢显得很重要。比如，若G中负权边教很少时，可 以先忽路（相当于删除）它们而采用Dijkstra算法，这样可以得到-个结点序，井把从： 到各点的无负权边时的最短路长度作为上界。用它取代步骤a,就能有效地提高算法的效 率。 例2.6.4对图2.25采用这样改进后的运算结果是： a.r(1)=0,π(2)=7，π(3)=8，x(4)=10,r(5)=8,π(6)=9， 因此结点序是(1,2,3,5,6,4)。 b.r(2)=7,(3)=6,x(5)=8,π(6)=8，π(4)=10。 b.π(2)=7，π(3)=6，r(5)=8,r(6)=8,π(4)=10。 2.7关键路径 -项工程任务，大到建造一座水坝，一枚航天火箭，一座体育中心，小至组装一台机 床，一架电视机，都要包括许多工序。这些工序相互约束，只有在某些工序完成之后、一…个 工岸才能开始。即它们之间存在完成的先后次序关系，一般认为这些关系是预知的，而且 也能够预计完成每个工序所需要的时间。这时工程领导人员迫切希望了解最少粉要多少 时间才能够完成整个工程项月，影响工程进度的要害工序是哪几个？ 本节我们只研究其中的一种特例，即工序之间只存在时间次序的约束，也就是说果 某工序；尚未完成，工序方就不能启动。这样，工程可以被分解为一些基本心序，序所 斋时间用，表示，工序之间的钓束情况可以用边来表示。这样可以得到两种类型的图。 2.7.1PT图 在PT(Potentialtask graph)图中，用结点表示工序，如果工序i完成之后工序j才能 启动，则图中有-条有向边(i,),其长度，表示工序i所需的时间。 ·28·
例2.7.1建造一座楼房底层的工序共有10个，如表2.7.1所示。各工序所需的时 间是陶定的， 表2.1.} 名称 所斋时回（天） 先序工序 1 基酬设施 15 卜部醐酸 电线安装 Y 4 阖梁支模 2 水暖管道 4 大染安装 2 4,5 楼瓶沼装 2 6,9,10 楼板浇慎 3 6,9,10 9 吊装楼梯 3 4,5 10 七部砌砖 2 相应的门图是图2.26。图中℃：表示作业i,以为始点的边权是作业，的时间。作 业，最早开始时间应在以为终点 的作业完成之后。例如作业，只能在 15 20时刻才能开始，23时刻才能完成， 而作业器2：时刻才能完成，因此 作业，最早只能在24时刻才能开 15 始。因此，作业，的最早开始时间恰 是，到的最长路径长度，整个工程 的最早完工时间是山到的最长路 长度， 这种阅必定不存在有向画路，否 图2.26 则某些工序将在自身完成之后才小能开始，这显然不符合实际情况。 引理2.7.1不存在有向回路的图G中，一定存在负度及正度为零的结点。 旺明：在G中构造一条极长的有向道路P,设P的始点为，终点为，就有d(u) 0.d“(,)0:假定d·(,)≠0，则-一定有边(，，)∈形(G),若a∈P,那么G存在有向 问路：若兵P,则P不是极长道路。因此d(:)=0。同理可证d(e,)=0。 在T图增加两个虚拟结点和，使所有负度为0的结点都是o的直接后继， 所有正度为0的洁点邵是的直接前趋。这些边的权都为0，这样得到的图G仍然不存 在有向回路 定理2.7.1设G不存在有向回路，可以将(G的结点重新编号为，，…，，使得 对任意的边，)EE(G),都有i<j。 所明：由引理2,7.1，G中存在，满足d()=0.对之重新编号为。在G中删去 ,得到，”“(；一，（是(G的导出子图，因此也没有负回路，这样可以将G中某个负度为 0的结点重新编号为：，再作(G一，依此类推。可将G的全部结点重新编号。此时，G中 所有的边都是从褊号小的结点指向编号大的结点，否则与编号的原则相悖。 ·29·
这样编号以后，假定到各点的最长路径长度依次是 0=π()，r(),…,r(), 则 π(，)=nax(π()十w(,u), Isisi 这就是最长路径算法的基础。 算法1.最长路径算法。 8.对结点重新编号为，，…。 b.π()-0 c.对j从2到n,令 r(v,)=max(r()十w(,)。 ver-(v) d,结束。 由于结点编号时只判别负度为0的结点，如果已经水出每个结点的负度，那么当需要 的，如“直接后继的负濩都减1，因 骤a需要m次减法和判断。同理，在步骤b计算r()时，只要判断它的直接前趋t,所以 b总共需要m次加法和比较。综上算法1的计算复杂性是O(m)。 由前所述，算法1所得到的最长路径是一条关键路径。其长度即是整个工程最早的完 工时间。因此，这条路径上的工序是不能延误的，否则将影响工程的完成。但是对于不在 关键路径上的工序，是否允许延误？如果允许，最多能够耽误多长时间呢？ 设π(，)是工程完工的最早时间，工序i的最晚肩动时间应该是 x(,)=r(y)一r(a), 其中x(,)表示，到un的最长路长度。 v,到v的最长路径等于G的转置（即其权矩阵的转置所对应的图）中o,到山，的最 长路径。因此把G的各边方向倒置而权值不变就得到G。由于G不含有向回路，故G矿也 不含有向回路。所以G中飞.到各点的最长路径同样可以调用算法1实现，从而得到每个 结点：的最晚启动时同t(,)。 是否还有更好的计算方法呢？我们发现算法1步骤执行之后，由于每个结点到结 点的最长路径长度可以按如下公式计算： r(,')=maxr(z,)+w(,), VE) 因而只要对结点采用逆序，依次求出π(，)=0，π(-，·)，，就可以实现。于是 得到 第法2.（已结点避新编号） a.t()=r(l）. b.对j从(n一1)到1，令 r(vj)=min ((v.)-w(u,v). E: c.结求。 这样(G中每个结点)，都具有2个值：最早启动时间π()和最晚启动时间x()。鼠然 工.序i的允许延误时间是t)=(）…()。 ·30·