计算机算法基础 第2版 习题及答案 第10章

PAGE16第10章 单源最短路径以图10-1为例，用Dijkstra算法找出下面无向图中以顶点s为源点的最短路径树。33810742abscde4158411解：和书中图10-1类似，下图(a)显示各点v的d(v)和p(v)初始值。图(b)-图(g)逐步显示每一次循环后，这棵最短路径树增长的情况及被更新各点v的d(v)和p(v)值。树中各点和边用粗线表示，有父子关系的边加上了方向，从父亲指向儿子，这不表示原来图是有向图，而是表示最短路径的取向。图(h)显示了算法结束后的最短路径树及源点s到各点的距离。10107842abscd4158411d(a)=(a)=nild(c)=(c)=nild(b)=(b)=nild(d)=(d)=nild(s)=0(s)=nil(a)初始化3ed(e)=(e)=nil107842abscde4158411d(a)=10(a)=sd(c)=15(c)=sd(b)=7(b)=sd(d)=(d)=nild(s)=0(s)=nil(b)顶点s被选中，更新a，b，cd(e)=(e)=nil310107842abscde4158411d(a)=10(a)=sd(c)=15(c)=sd(b)=7(b)=sd(d)=15(d)=bd(s)=0(s)=nil(c)顶点b被选中，更新d，ed(e)=18(e)=b3107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(d)顶点a被选中，更新c，dd(e)=18(e)=b310107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(e)顶点c被选中，更新ed(e)=17(e)=c3107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(f)顶点d被选中，更新ed(e)=16(e)=d310107842abscde4158411d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(g)顶点e被选中，无更新点d(e)=16(e)=d31072abscde4d(a)=10(a)=sd(c)=13(c)=ad(b)=7(b)=sd(d)=14(d)=ad(s)=0(s)=nil(h)算法产生的最短路径树d(e)=16(e)=d3以图10-3为例，用Bellman-Ford算法找出下面有向图中以顶点s为源点的最小最短路径树。每轮松弛遍历所用的边的顺序请按字母顺序确定，即(a,b)，(a,c)，(a,e)，(b,c)，(b,d)，(c,d)，(c,e)，(d,e)，(s,a)，(s,b)，(s,d)。-3-3-1105-24abscde978-2-3解：和书中图10-3类似，下图(a)显示各点v的d(v)和p(v)初始值。图(b)-图(c)显示了前2轮松弛遍历的结果。有父子关系的边用粗线表示。因为从第3轮开始，松弛遍历不产生任何更新，所以省去3轮的显示。图(d)显示算法结束后的最短路径树及源点s到各点的距离。(a)(a)初始状态，源点是顶点sd(a)=(a)=nild(c)=(c)=nild(e)=(e)=nild(d)=(d)=nild(b)=(b)=nild(s)=0(s)=nil-3-1105-24abscde978-2-3(b)第1轮松弛遍历后各点的暂时距离d(a)=10(a)=sd(c)=(c)=nild(e)=(e)=nild(d)=-3(d)=sd(b)=5(b)=sd(s)=0(s)=nil-3-1105-24abscde978-2-3(c)(c)第2轮松弛遍历后各点的暂时距离d(a)=10(a)=sd(c)=7(c)=ad(e)=1(c)=dd(d)=-3(d)=sd(b)=5(b)=sd(s)=0(s)=nil-3-1105-24abscde978-2-3(d)算法产生的最短路径树d(a)=10(a)=sd(b)=7(b)=ad(e)=1(c)=dd(d)=-3(d)=sd(c)=5(c)=sd(s)=0(s)=nil-31054abscde-3假设G=(V,E)是一个加权有向图。图中的每个顶点代表一个通讯网络的结点，而边(u,v)ÎE的权值r(u,v)则表示u和v两点间信道的可靠性，其范围是区间[0,1]中实数，0£r(u,v)£1。我们把r(u,v)理解为u和v两点间信道正常工作(不出故障)的概率，并假定每条边的这个可靠性与其他边的可靠性是独立无关的。请设计一个复杂度好的算法找到一条从顶点s到顶点t的最可靠路径。解：我们可以把Dilkstra算法稍加修改后直接解出这个问题，也可以把这个问题先转化为一个最短路径问题，然后用Dijkstra算法解出。这两个算法都算出从s到每一个其他顶点的最可靠路径,当然也包括顶点t，也就是算出以s为源点的最可靠路径树。我们知道，如果p(s,v)是一条从s到顶点v的路径，那么这条路径的可靠性，记为R(p(s,v))，是路径上所有边的可靠性乘积：R(p(s,v))=(x,y)∈p(s,v)r(x,y)。方法一:对Dijkstra算法稍做修改后算法如下：SS-Most-Reliable-Path(G(V,E),s)foreachvÎV //初始化，没有路径到v，可靠性为0 r(v)¬0 //目前找到的最可靠路径的可靠性，初始为0 p(v)¬nilendforr(s)¬1 //从源点到源点，始终是可靠的V(A)¬ //与边的集合A关联的顶点空集，初始为空A¬ //初始，边的集合是空集constructT(V(A),A)Q¬V //一开始，所有点都在树外whileQ¹ u¬Extract-Max(Q) //找出有最大r(u)值的顶点u A¬A{(p(u),u)} V(A)V(A){u} foreachvÎAdj(u) //更新顶点u的邻居 ifr(u)´r(u,v)>r(v) //如果经过顶点u的路径更可靠，更新r(v) then r(v)¬r(u)´r(u,v) p(v)¬u endif endforendwhilereturnT(V(A),A) //输出最可靠路径树End这个算法的正确性及复杂度可以像证明Dijkstra算法那样证明，这里略去。方法二:我们先把图G转换为新图G’(V’,E’)使得V’=V，E’=E。两个图的区别在于边的权值。对新图G’(V’,E’)中边(u,v)ÎE’，我们赋以权值w(u,v)=-lgr(u,v)。因为0£r(u,v)£1，我们有0£-lgr(u,v)£¥。这样一来，在图G’中的路径p(s,t)的加权长度为：w(p(s,t))==-lg=-lgR(p(s,v))。所以，在G’中的最短路径在G中就是一条最可靠路径，反之亦然。因此，G中以s为源点的一棵最可靠路径树也就是G’中一棵以s为源点的最短路径树，而后者可以用Dijkstra算法解出。(最宽路径问题)让我们重温一下在第9章习题12中我们介绍的最宽路径问题。在加权连通图G(V,E)的一条路径上权值最小的一条边称为这条路径的瓶颈，而这条路径的宽度定义为它的一条瓶颈边的权值。图G中从顶点u到顶点v的所有路径中宽度最大的一条路径称为从u到v的最宽路径。当然，这个定义也适用于有向图。在第9章习题12中我们证明了G的最大支撑树T中任意两点之间的路径都是G=(V,E)中这两点间的最宽路径。可是，用最大支撑树T来找最宽路径的方法不能直接应用到有向图。请把Dijkstra算法修改为一个可以为有向图计算从一源点s到其他各点的最宽路径树，称为单源最宽路径树。你需要证明算法的正确性，特别要证明，既使图中有源点可达负回路，算法也是正确的。解：修改后的算法如下。SS-Widest-Path(G(V,E),s)foreachvÎV d(v)¬- //初始化，没有路径到v，宽度d(v)为- p(v)¬nilendford(s)¬ //从源点到源点，宽度d(s)为无穷大V(A)A //一开始，最宽路径树没有边constructT(V(A),A)Q¬V //所有点vV以d(v)为关键字，组织在优先队列Q中whileQ¹ u¬Extract-Max(Q) //找出有最大d(u)值的顶点u，第一轮必定是s A¬A{(p(u),u)} V(A)V(A){u} foreachvÎAdj(u) //更新顶点u的邻居 ifmin{d(u),w(u,v)}>d(v) //如果经过顶点u的路径更宽，更新d(v) then d(v)¬min{d(u),w(u,v)} p(v)¬u endif endforendwhilereturnT(V(A),A)End正确性证明：我用用归纳法证明。在证明过程中，我们允许权值为任何实数，所以算法允许负数和负回路。一个有用的观察是，如果从源点s到顶点v的路径上经过一个回路，那么，不论是正回路还是负回路，把这个回路从路径上摘去后所得到的路径只会更宽不会更窄。所以，既使有负回路，一定有一条从顶点s到顶点v的最宽路径是简单路径。下面我们用归纳法证明以下命题：算法在初始化之后第10行开始的循环中，每次循环确定一条最宽路径，即从源点s到选中的顶点u的最宽路径，其宽度为d(u)。归纳基础：第1次循环一定选中源点s。因为从源点s到s不需经过任何边，d(s)=显然是正确的。归纳步骤：假设经过k次循环后(1k<n)，从源点s到k个点的最宽路径都已正确地确定。而且，从源点s到这k个点中任一顶点z的最宽路径的宽度是d(z)。现在证明，如果第k+1次循环中选中的是顶点u，那么从源点s到(u)再到u是一条从源点s到u的最宽路径，其宽度为d(u)。为了用反证法证明，我们假设这条路径不是最宽的，最宽路径是p(s,u)，其宽度是d(p(s,u))>d(u)，我们将导出矛盾。让我们定义一个割，C={S,V-S}，其中S是前面k次循环得到的树中的k个点，而V-S是树外的n-k个点。这条比d(u)还宽的路径p(s,u)含有至少一条交叉边。设(x,y)是路径p(s,u)上第一条交叉边。如下图所示，我们可以把p(s,u)分为三段:第1段是树里从s到x的路径，p1，根据假设，它的宽度为d(p1)=d(x)。第2段p2是边(x,y)，其宽度为w(x,y)。 第3段是y到u的路径，p3，它的宽度为d(p3)。ssxySp1p3d(y)d(u)d(y)V-Su割C=(S,V-S)p2=(x,y)树中k个点d(x)由定义，路径p(s,u)的宽度为d(p(s,u))=min{d(p1)，w(x,y)，d(p3)}=min{d(x)，w(x,y)，d(p3)}由反证假设，d(p(s,u))>d(u)，所以有min{d(x)，w(x,y)，d(p3)}>d(u)因为min{d(x)，w(x,y)}min{d(x)，w(x,y)，d(p3)}，我们有min{d(x)，w(x,y)}>d(u)因为顶点x是早先被选入树中的k个点之一，而min{d(x)，w(x,y)}恰恰是在顶点x被选中时向邻居y提供的路径的宽度，也就是用来更新d(y)的值。所以，必有d(y)min{d(x)，w(x,y)}。否则的话，顶点y在那个时刻应该更新而没有更新，违反了算法。所以，我们必有如下关系：d(y)min{d(x)，w(x,y)}>d[u]，即d(y)>d(u)。这与算法矛盾，因为算法在选取第k+1个点u时，它的d(u)值是所有树以外的顶点中最大的，包括顶点y在内。这个矛盾说明不存在比d(u)还宽的路径，归纳成功，命题正确。命题正确直接证明了算法的正确。一个传感器网络(sensornetwork)可以用一个加权有向图G(V,E)来建模。图中的每个顶点代表一个传感器(sensor)，而每条边(u,v)表示从传感器u可以用无线电频道送信息给传感器v。我们假定每个传感器u都是用电池来工作的。每当边(u,v)使用一次，即传感器u向传感器v传输一个单位信息，传感器u需要消耗能量w(u,v)。如果传输前传感器u的能量是P(u)，那么传输后它的剩余能量就是P(u)-w(u,v)。接收信息的传感器v消耗的能量可忽略不计。当传感器u的能量少于某个值时就不能工作而使整个网络瘫痪。现在，我们希望在网络中找一条从顶点s到顶点t的路径来传输一个单位信息。传输前每个传感器u的能量已知为P(u)，传输后，路径上各点的能量会得到不同的减少。其中剩余能量最少的点威胁着网络的安全。这个有最少剩余能量的顶点称为是这条路径的瓶颈点。请设计一个复杂度好的算法找到一条从顶点s到顶点t的路径使得传输后这条路径的瓶颈点的剩余能量最大。(提示：用第4题结果。)解:我们从加权有向图G(V,E)来构造一个新的加权有向图G’(V’,E’)。其中V’=V,E’=E。因为当边(u,v)使用后，传感器u的能量变为P(u)-w(u,v)，我们用w’(u’,v’)=P(u)-w(u,v)表示使用边(u,v)后传感器u的剩余能量。这样一来，G中一条路径的瓶颈点就变成G’中对应路径的瓶颈边。因此，在G中找一条从顶点s到顶点t有最大瓶颈点剩余能量的路径就等价于找一条G’中从顶点s’到顶点t’的最宽路径。算法的伪码如下：Max-Min-Path(G(V,E)) V’¬V //顶点v’vE’¬E //(u’,v’)(u,v)foreachedge(u,v)ÎE //给G’(V’,E’)中边赋权值 w’(u’,v’)¬P(u)-w(u,v)SS-Widest-Path(G’(V’,E’),s’) //调用第4题算法在G’中找出以s’为源的最宽路径树p(s,t)¬p(s’,t’) //G’中从顶点s’到顶点t’的最宽路径就是解returnp(s,t)End假设G=(V,E)是一个加权有向图并且从源点s为出发点的边中可能有负数的权值，但其他边的权值没有负数，并且图中没有负回路。证明Dijkstra算法仍可以正确解决单源最短路径问题。解：我们仍用归纳法证明以下命题：当顶点u被选中而连到树上去时，d(u)值就是从源点s到顶点u的最短矩离，对应的最短路径是从源点s到u的父亲顶点p(u)，再到u。归纳基础：从算法可知，因为d(s)=0<¥，第一个被选中的点必定是源点s。因为图中没有负回路，没有一条从s到s的路径会有小于零的长度，显然这是个正确的距离。归纳步骤：假没算法已经正确地选取了k个顶点在树中(1£k<n)，即树中从源点s到这k个顶点的任一个点z的路径都是从源点s到该点的一条最短路径，长度为d(z)。现在证明算法选取的第k+1个顶点u也是正确的，也就是要证明d(u)一定是一条最短路径的距离。我们用反证法来证明它。假设图中还有一条比d(u)还短的路径p(s,u)，w(p(s,u))<d(u)。我们将由此导出矛盾。首先，因为没有负回路，我们可以假定路径p(s,u)是条简单回路。其次，让我们定义一个割，C={S,V-S}，其中S是树中的k个点，而V-S是树外的n-k个点。这条比d(u)还短的路径p(s,u)含有至少一条交叉边。设(x,y)是从源点s出发的这条路径上第一条交叉边。如下图所示，我们可以把路径p(s,u)分为三段:第1段是树里从s到x的路径，p1，根据归纳假设，它的长度为w(p1)=d(x)。第2段p2是边(x,y)，其长度为w(x,y)。第3段是y到u的路径，p3。因为p(s,u)是条简单回路，p3不经过源点s，故有w(p3)³0。ssxySp1P3d(y)d(u)£d(y)V-Su割C=(S,V–S)p2=(x,y)树中k个点由假设，w(p(s,u))=w(p1)+w(x,y)+w(p3)<d(u)。因为w(p3)³0，我们有w(p1)+w(x,y)<d(u)，也就是w(x)+w(x,y)<d(u)。可是，因为顶点x是早先被选入树中的k个点之一，而d(x)+w(x,y)恰恰是在顶点x被选中时向邻居y提供的用以更新d(y)的距离。所以，必有d(y)£d(x)+w(x,y)。否则的话，顶点y在那个时刻应该更新而没有更新，违反了算法。所以，我们必有如下关系：d(y)£d(x)+w(x,y)<d(u)，即d(y)<d(u)。这与算法矛盾，因为算法在选取第k+1个点u时，它的d(u)值是所有树以外的顶点中最小的，包括顶点y在内。这个矛盾说明不存在比d(u)还短的路径，归纳成功。假设G(V,E)是一个加权有向图并且边的权值函数是w:E®{0,1,…,W}，这里W是一个正整数。请修改Dijkstra算法使之能在O(Wn+m)时间内算出以顶点s为源点的最短路径树。解: 我们需要设计一个数据结构Q使得Dijkstra算法的每次循环中以下两件事情可以做得比较快：u¬Extract-Min(Q)，如果d(u)+w(u,v)<d(v)，更新u的邻居v的d(v)值。我们一共要做n次第一件事，m次第二件事。我们注意到任一条最短路径最多有(n-1)条边，其加权长度一定在区间[0，(n-1)W]内。所以，我们为每一个可能的暂时距离的值定义一个集合：L[k]={u|d(u)=k}(0£k£(n-1)W)，L[(n-1)W+1]={u|d(u)=¥}。也就是说，所有暂时矩离相同的点放在一个集合中，并用链表把它们串起来，一共有(n-1)W+2个集合。顶点u的暂时矩离是d(u)，所以，它所在的集合是L[d(u)]。初始化时，除源点s外的所有点都在集合L[(n-1)W+1]中。现在来看看我们如何来做上述两件事。当我们要做第一件事时，我们就按L[0]，L[1]，L[2]，…顺序寻找第一个非空集合。这第一个非空集合中的顶点都有最短的暂时距离。我们任取一个即可。但是，真这样做，时间会很长。我们注意到，因为每次选中的点的暂时距离是单调递增的。如果我们上次是在L[k]中选到一顶点，那么这次我们只需要从L[k]开始寻找，因为L[0]，L[1]，L[2]，…，L[k-1]表必定为空且永远为空。假设我们从L[k]开始寻找，如果L[k]非空，那我们只需O(1)时间即可完成第一件事。如果L[k]是空集，那我们就要查看L[k+1]。发现L[k]是空集并进入L[k+1]需要的时间是O(1)。这种发现空集的情况总共最多有(n-1)W+1次，所以做第一件事总共需要O(Wn)时间。每次循环中的第二件事就是更新u的邻居v的d(v)值。当d(u)+w(u,v)<d(v)时，我们就把v从链表L[d(v)]中摘除，然后把它插到链表L[k]中，这里k=d(u)+w(u,v)。所以这第二件事只需常数时间O(1)。因为算法一共需要做n次第一件事，m次第二件事，算法的复杂度是O(nW+m)。下面是祥细的伪码。Modified-Dijkstra(G(V,E),s)Initialize-single-source(G,s) //初始化，与原Dijkstra算法同fork0tonW L[k]¬ //建立链表L[k]endforL[0]¬{s}L[(n-1)W+1]¬V–{s}minset¬0 //最小非空集合的号码V(A)Awhileminset¹(n-1)W+1 ifL[minset]¹ then u¬Extract(L[minset]) //抽取一个顶点 AA{((u),u)} V(A)V(A){u} foreachvÎAdj(u) ifd(u)+w(u,v)<d(v) then L[d(v)]¬L[d(v)]–{v} d(v)¬d(u)+w(u,v) (v)¬u L[d(v)]¬L[d(v)]È{v} endif endfor elseminset¬minset+1 endifendwhilereturnT(V(A),A)End假设我们需要沿一条长为l公里的公路两侧布置一些炮兵阵地，使得整个公路都在炮火控制之下。假设有n个可供选择的炮兵阵地，顺序标以1，2，…，n。因地形的差异，每个阵地可配备的火炮数量不同，而且只能控制一小段公路。假设阵地i(1≤i≤n)可以控制从S[i]到E[i]的一段。这里S[i]和E[i]分别是这一小段公路两端与公路起点的距离，0≤S[i]<E[i]≤l。另外，假定构筑阵地i需要费用C[i]>0。下图是一个n=7的例子。CC[7]=4l=5公里2.3123C[1]=3C[2]=2C[3]=6S[1]=01.20.3C[5]=30.91.851.64C[4]=83.44.43.66C[6]=53.84.17E[1]S[2]E[3]E[6]E[7]E[5]S[5]S[6]S[7]E[2]S[3]S[4]E[4]假定在所有阵地上都布置炮位，整个公路可以复盖，但代价太大。我们希望从中找出一部分阵地使得整个公路可以复盖，而且总的费用最小。例如，在上面的例子中，我们可选阵地1，3，5，7，总代价是C=C[1]+C[3]+C[5]+C[7]=3+6+3+4=16，可以证明是最好的。请用上例解释怎样把这个优化问题建模为一个图的最短路径问题解出(伪码不要求)。解: 因为n个阵地顺序编号，故有S[1]S[2]…S[n]。我们构造一个有向图，步骤如下：为阵地i建一个顶点vi(1≤i≤n)。如果有S[i]<S[j]≤F[i]<F[j](1i<jn)，则构造一条边(vi,vj)。这就是说，如果两段公路相交但不互相包含，则有一条边，从离公路起点近的阵地指向后者。给边(vi,vj)赋一权值w(vi,vj)=C[i]。加上一个顶点s。如果S[i]=0(1≤i≤n)，则建一条边(s,vi)，并赋权值w(s,vi)=0。这样的阵地i一定存在，否则不可能复盖整个公路。加上一个顶点t。如果F[j]=l(1≤j≤n)，则建一条边(vj，t)，并赋权值w(vj，t)=C[j]。这样的阵地j一定存在，否则不可能复盖整个公路。以上面图形为例，构造的有向图如下：vv1v2v3v6v7v5v4ts04533226633888图构造好之后，图中的一条从s到t的路径对应一种选择方案，该路径的总权值就是该方案的总费用。所以，找到从s到t的最短路径也就解决了这个优化问题。以上面图为例，一条最短路径用粗线标出，它对应的解是{1，3，5，7}，总费用为16。因为这个图无回路，可以用拓扑排序后线性时间解出。算法的主要工作在构造这个图，其复杂度显然是O(n2)。假设有向图G(V,E)中边的权值都是正数，|V|=n,|E|=m。P(s,t)是图G(V,E)中从点s到点t的一条最短路径。我们希望找一条从点s到点t的第二短路径，也就是说，在所有与P(s,t)不同的简单路径中，找一条最短的路径。这条路径只要有任何一条边与P(s,t)不同即可，这条路径也许和P(s,t)一样长，也许不存在。请设计一个O(n3)或更好算法找到这条第二短路径，或报告不存在，并证明正确性。解： 假设P(s,t)是图G(V,E)中从点s到点t的一条最短路径。我们注意到，如果第二短路径存在，它不可能包含路径P(s,t)的所有边。这是因为，在路径P(s,t)上加上任何边的路径不可能是条简单路径。所以，我们的做法是，每次从图G(V,E)中删去一条P(s,t)的边，然后在删去这条边的图中找一条从点s到点t的最短路径。如果P(s,t)有k条边，我们需要对k个图求从点s到点t的最短路径。那么，最短的一条就是解。伪码如下。Second-Shortest-Path(G(V,E),P(s,t))dpathforeachedgeeP(s,t) E’E–{e} SSP-Dijkstra(G(V,E’),s) //为每点v计算最短路径p(s,v)，长为d(v) ifd(t)<d then dd(t) pathp(s,t) //这一步需要构造路径，略去细节 endifendforifd= thenreturn(Nosecondpathatall) elsereturnpath,dEnd因为第5行调用算法SSP-Dijkstra最多n-1次，如果我们用数组作为优先队列，上述算法有复杂度O(n3)。如果我们用斐波那契堆作为优先队列，上述算法有复杂度O(n2lgn+mn)。假设有向图G(V,E)中边的权值都是正数，|V|=n,|E|=m。虽然我们可以用Dijkstra算法得到一棵以源点s为根的最短路径树T，但树T只提供一条从源点s到其它每一个顶点v的最短路径。有时我们希望知道是否还有一条不同的最短路径。请设计一个O(n2)算法，为每个顶点v判断有几条不同的从源点s到顶点v的最短路径。并且，如果不止一条，它要为顶点v找出两条不同的最短路径，否则报告不存在。请证明算法的正确性。解: 我们先用Dijkstra算法得到一棵以源点s为根的最短路径树T。树T中，从源点s到每个顶点v的路径是一条最短路径，长度是d(v)。为方便，我们假定，源点s有路径到达所有顶点。让我们取一点v来考虑。假设顶点u是v的一个反向邻居，而且d(u)+w(u,v)=d(v)，那么从源点s到顶点u，再到顶点v就是一条最短路径。进一步，如果从源点s到顶点u有h条最短路径，那么顶点u就可以向顶点v提供h条最短路径。反之，如果有一条从源点s到顶点v的最短路径<s,u1,u2,…,uk,v>，那么，顶点uk必定是v的反向邻居，路径<s,u1,u2,…,uk>必定是从源点s到顶点uk的最短路径，并且有d(uk)+w(uk,v)=d(v)。让我们定义N(v)为从源点s到顶点v的不同的最短路径个数，那么，我们有以下归纳公式：N(s)=1，N(v)=d(u)+wu,v由以上观察，我们下面的算法判断有几条不同的从源点s到顶点v的最短路径。由上面讨论，正确性显然。Number-of-Shortest-Path(G(V,E),s)SSP-Dijkstra(G(V,E),s) //求最短路径树T，p(s,v)是最短路径，(s,v)=d(v)G’(V,E’)T(V(A),A) //复制一个最短路径树TEE–A //树T以外的边的集合foreachedge(u,v)E ifd(u)+w(u,v)=d(v) thenE’E’{(u,v)} //在树里加上这些边 endifendfor //显然，G’(V,E’)不含回路Topological-Sort(G’(V,E’))Let<v1,v2,…,vn>bethesequencefromTopological-Sort //显然有v1=sN(v1)1fori2ton N(vi)0 //初始化endforfori1ton-1 foreachvAdj(vi) N(v)N(v)+N(vi) endforendforcompute(G’)T //找G’的转置矩阵以便找到反向邻居Adj-(v)fori1ton //下面报告两条最短路径 ifN(vi)=1 thenreturn(Onlyonepathp(s,vi)) //p(s,vi)是最短路径树里路径 else if|Adj-(v)|2 //点v有两个反向邻居 thenchoosetwobackwardneighbors,u1andu2 Path-1(v)p(s,u1){(u1,v)} Path-2(v)p(s,u2){(u2,v)} outputPath-1(v),Path-2(v) else u(v) //u是最短路径树里v的父亲 Path-1(v)Path-1(u){(u,v)} Path-2(v)Path-2(u){(u,v)} outputPath-1(v),Path-2(v) endif endifendforEnd因为报告一条路径需要O(n)时间，所以算法有复杂度O(n2)。假设有向图G(V,E)中每条边(u,v)的权值是正数，w(u,v)>0。另外，每个顶点v也有一个正数的权值w(v)>0。图中一条从点s到点u的路径p(s,u)的长度定义为路径上所有顶点和边的权值总和，包括点s和点u，即w(p(s,u))=v∈p(s,u)wv+(a,b)∈p(s,u)w(a,b)。对于这样定义的路径长度，请设计一个与Dijkstra算法有相同复杂度的算法，为有向图G(V,E)计算以顶点s解：我们只需稍稍改动Dijkstra算法即可。因为很简单，改动处在伪码中说明。算法伪码如下：SSP-with-Weighted-Vertices(G(V,E),s)foreachvÎV d(v)¬¥p(v)¬nilendford(s)¬w(s) //改动处1，d(s)初始值从0改为它的权值w(s)V(A)¬ A Q¬