最短路径算法--Dijkstra 算法,Bellmanford 算法,Floyd 算法,Johnson 算法.pdf

6.3.3 最短路径算法-Dijkstra 算法,Bellm anford 算法，Floyd 算法,Johnson 算法最短路径算法在交通地图上，两地点之间的路径通常标有长度，我们可以用加权有向来描述地图上的 交通网。加权有向图中每条路径都有一个路径权值，大小为该路径上所有边的权值之和。本 节将重点讨论顶点之间最短路径问题。在实际问题中，路径权值还可以表示其它类型的开销，例如两地之间行程所需要的时间；两任务切换所需代价等。本节讨论的最短路径具有方向性，问题用图的术语描述为：给定一个起始顶点S和一个 结束顶点t,在图中找出从S到t的一条最短路径。称S为路径源点，t为路径汇点。最短路径问题可以进一步分为单源最短路径和全源最短路径。单源最短路径定义为，给定起始顶点S,找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中 Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford 算法可以适用于更一般的问题，图中边的权值可以为负。全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算 法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可 以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包 含负环的图的全源最短路径问题，但是其算法效率更高。1基本原则最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径 上其它顶点的最短路径。具体描述为：对于给定的带权图G=(V,E),设p=vi,V2,V，是从V1到Vk的最短路径，那么对于任意i和j,lijk,Pij=d v+a(v,w)d w v+a(v,w);p w=v;2单源最短路径单源最短路径定义为，给定起始顶点S,找出从s到图中其它各顶点的最短路径。这里 我们将得到的结果称为最短路径树(shortest path tree),其中树根为起始顶点s。2.1 Di jkstra 算法在前面章节中讨论最小支撑树时，我们讨论了 Prim算法：每次选择一条边添加到最小 支撑树MST中，这条边连接当前MST中某个顶点和尚未在MST中的某个顶点，其权值最小。采用类似的方案可以计算最短路径树SPT。开始时将源点添加到SPT中，然后，每次增加一 条边来构建SPT,所取的边总是可以给出从源点到尚未在SPT中某个定点的最短路径。这样,顶点按照到源点的距离由小到大逐个添加到SPT中。这种算法称为Dijkstra算法，具体的 实现跟Prim类型，分为普通实现和基于最小堆的实现。首先，我们需要明确Dijkstra算法的适用范围是权值非负的图，即解决带有非负权值 的图中的单源最短路径问题。下面对这一属性做简单分析。给定顶点S,通过Dijkstra算法得到的最短路径树中，从根s到树中各顶点u的树路 径对应着图中从顶点s到顶点u的最短路径。归纳证明如下：假设当前所得到的子树具有这一属性，向当前子树中添加新的顶点u,满足：从顶点s 出发，经过当前SPT中的树路径，并最终到达u。可以通过选择，使得所选择的s到u的路 径比所有满足条件的路径都更短。所以增加一个新的顶点将增加到达该顶点的一条最短路 径。如果边的权值可以为负数，那么上述证明过程将不成立，上述证明中已经假设了向当前 子树中添加新的边时，路径的长度不会递减。然而在具有负权值的边的图中，这个假设不能 满足，因为所遇到的任何边都可能指向子树中的某个顶点，而且这条边可能有一个负权值，从而会使得到达该顶点的路径比树路径更短。以下是Dijkstra算法的实现，Dijkstra算法和基于优先队列的Dijkstra算法都在 Single Source Shortest Pa ths类中实现，类中包括存放每个顶点到源点的最近距离D 数组和存放各个顶点的在SPT中的父节点V数组。电/*Dijkstra算法寻找图中单源点最短路径夫输入为待寻找的图G以及源点s夫param s 起始顶点*/public void Dijkstra(int s)if(s 0)return;int nv=G.get_nv();/初始化for(int i=0;i (Dv+G.getEdgeWt(w)/更新最短距离DG.edge_v2(w)=Dv+G.getEdgeWt(w);/更新父节点VG.edge_v2(w)=v;System.out.printIn(rx(+w.get_vl()+，+w.get_v2()+G.getEdgeWt(w);)/根据V数组建立最短路径树SPTspt.addChild(s,s,new ElemItem(D0);spt.setRoot(s);int f=-1;/顶点标记数组，V_idxi=1表示i顶点已经在SPT中，否则不再SPT中int V_idx=new intV.length;/初始化for(int i=0;i V_idx.length;i+)V_idxi=0;/起始顶点s已经在SPT中V_idxs=1;while(true)f=-1；for(int i=0;i=0&V_i dxVi-一 1&spt.addChild(Vi,i,new ElemItem(Di)V_idxi=1;f=1；)/一次都没有添加，结束循环if(f=-1)break;)电算法中每次从SPT之外的顶点中选择一个顶点v,对应边的权值最小；然后对这条边进 行松弛操作。算法迭代直至图中所有顶点都在SPT中为止。以图为例，求解图的最短路径树，起始顶点为顶点0。根据算法实现过程，提取图中最 短路径数的过程如图(a-c)。图Dijkstra算法示例图算法初始化阶段每个顶点到起始顶点S的最短路径长度为8。首先从起始顶点0开始，寻找相邻顶点1和顶点5,并对其进行松弛操作。此时SPT中根节点为0,两个（未确定）子 节点为顶点1和顶点5。其中顶点0着色为灰色（赋值1,只有着色为灰色的顶点确定为SPT 中顶点。由于顶点1和顶点5对应的边可能会在以后的操作中进行松弛操作，所以SPT中这两个顶 点是未确定的，顶点着色也未改变。选择与当前SPT中顶点0最近的顶点5,首先将顶点5确定为SPT中顶点0的子节点；然 后对其相邻顶点进行松弛操作。相邻顶点为顶点1和顶点4,其中顶点4的最短距离需要更新。选择与当前SPT中顶点0、顶点5最近的顶点4,首先将顶点4确定为SPT中顶点5的子 节点；然后对其相邻顶点进行松弛操作。相邻顶点为顶点2和顶点3,这两个顶点都需要更 新最短距离。接下来将先后选择边(5,1)、(4,2)和(4,3),并进行松弛操作。最终得到的SPT为：将图作为算法代码的测试输入，编写示例程序如下:电public class DijkstraExample public static void main(String args)GraphLnk GL=Utilities.BulidGraphLnkFromFile(Graph、graph8.txtn);SingleSourceShortestPaths sp=new SinglesourceShortestPaths(GL);sp.Dijkstra(0);sp.spt.ford_print_tree();)算法跟踪顶点选择和边松弛操作的过程，每个顶点距离起始顶点的最短距离记录在数 组D中，顶点的父节点保存在数组V中，最终利用前面章节中讨论的广义树存放SPT。程序 运行结果为：relax(0,1),41 relax(0,5),29O found(0,5)f 2 9 relax(5,4),21O found(5 r 4),21 relax(4,2),32 relax(4,3),3 6O found(5,1),2 9O found(4,2),32O found(4,3),366节点，前序遍历打印：I-0.0(0)|-41.0(1)|-29.0(5)|-50.0(4)I-82.0(2)|-8 6.0(3)结果第一部分为算法将各顶点添加到SPT中以及各条边的松弛操作。第二部分表示算法 最终获得的SPT树。读者可以自行对照并理解示例程序的运行结果和上面分析步骤。在前面章节中，Prim算法可以借助于优先队列（最小堆）来提高效率，这里也可以采 用这种策略。具体算法过程其读者自行理解，本书提供该算法的实现，具体参见程序。通过 分析可以发现基于最小堆的Dijkstra算法的时间开销与E/gV成正比。2.2 Bel ImanFord 算法Bellman-Ford算法诞生于20世纪50年代，对于不包含负环的图，该算法可以简单有效 地求解图的单源最短路径问题。算法的基本思路非常简单：以任意顺序考虑图的边，沿着各 条边进行松弛操作，重复操作IV|次（|V|表示图中顶点的个数）o对有向带权图G=V,E,从顶点s起始，利用Bellman-Ford算法求解各顶点最短距 离，算法描述如下：for i=0;i|V|;i+for each edge u,v ERELAX u,v 算法对每条边做松弛操作，并且重复IVI次，所以算法可以在于|V|E|成正比的时间 内解决单源最短路径问题。算法I分简单，但是在实际中并不被采用，对其做简单的改进就 可以得到更高效算法。我们对算法的正确性做简单分析。设每个顶点距离起始顶点s的最短距离存放在数组D 中。我们首先假设以下命题为真：算法在第i遍处理之后，对于所有顶点u,Du不大于s 到u且包含i条（或更少）边的最短路径的长度。根据以上命题，经过|V|-1次迭代后，对所给定的顶点u,Du为任何从s到u且包含 IV|-1条（或更少）边的最短路径的长度的下界。此时算法可以停止迭代，因为包含|V|条边（或更多）的任何路径将必然有一个环，通过去除这个环将可以找到一条包含|V|-1（或更 少）边的路径，该路径长度不大于去环前的路径的长度。所以Du同时又是从s到u的最 短路径的上界，既然Du同时是下界和上界，那么必然是最短路径的长度。下面我们对上述命题做归纳证明。i为0时，命题自然为成立；假设命题对于i成立，那么对于每个给定的顶点u分两种情况：,在从s到u包含i+1条（或更少）边的路径中，如果其中最短路径长度为i（或更 少）,那么Du不做调整。否则，有一条从S到U且包含i+1条边的路径，其长度比S到U且包含i（或更少）条边的任何路径都短。该路径必然由S先到达某个顶点W的路径再加上边 w,U）所组成。由归纳假设，Dw是从S到W的最短距离的上边界，而且第i+1遍处理会 对各条边进行检查。所以算法在第i+1遍处理之后，对于所有顶点U,Du不大于S到u且包含i条（或更 少）边的最短路径的长度然而算法每遍处理对于各条边都进行检查将是很大的浪费，因为有大量的边并不会导致 有效的松弛。事实上，唯一可能导致调整的边仅为某些特定顶点出发的边：这些顶点的值在 上一遍处理中发生了变化。那么可以对算法进行优化，即每遍处理只对特定顶点出发的边做松弛操作。可以将发生 变化的顶点的记录下来，在下一遍处理时对一这些顶点为源点的边做松弛操作。我们使用队 列结构来存储这些顶点，以下是算法的实现，算法在MinusWeightGraph类中实现，类 中包括存放每个顶点到源点的最近距离D数组和存放各个顶点的在SPT中的父节点V数组。电/*Bellman-Ford算法求解给定图的单源最短路径；*图中边的权值可以是负数。*param s 起始顶点*/public void BellmanFord(int s)if(s 0)return;int nv=G.get_nv();/初始化for(int i=0;i nv;i+)Di=Double.MAX_VALUE;Vi=-2;G.setMark(i,0);)/队歹UQLinkQueue Q=new LinkQueue();/起始顶点的距离为0D s =0;/将起点s和nv添加到队列中int M=Integer.MAX_VALUE;Q.enqueue(new Elemltem(s);Q.enqueue(new Elemltem(M);System.out.print();Q.printQueue();/迭代过程，直到Q为空while(Q.currSize()!=0)int f=-1;int v,N=0;while(M=(v=(Integer)(Q.dequeue().elem).intValue()if(N+nv)f=1;break;Q.enqueue(new Elemltem(M);)System.out.print(n0);Q.printQueue();if(f=1)break;/对v的所有相连的边efor(Edge e=G.firstEdge(v);G.isEdge(e);e=G.nextEdge(e)/更新e的终点w的距离int w=e.get_v2();double P=Dv+G.getEdgeWt(e);/如果w经过v的路径更短，则更新w的距离if(P Dw)D w=P;/将w添加到队列中Q.enqueue(new Elemltem(w);/将w的父节点重置为vV w=v;)System.out.print(n);Q.printQueue();)/根据V数组建立最短路径树SPTmst.addChild(s,s,new ElemItem(Ds);mst.setRoot(s);int f=-1;/顶点标记数组，V_idxi=1表示i顶点已经在SPT中，否则不再SPT中 int V_idx=new intV.length;/初始化for(int i=0;i V_idx.length;i+)V_idxi=0;/起始顶点s已经在SPT中V_idxs=1;while(true)f=-1；for(int i=0;i=0&V_idxVi1&mst.addChild(Vir i,new ElemItem(Di)V_idxi=1;f=1；)/一次都没有添加，结束循环if(f=-1)break;)算法实现过程中，用无穷大数Integer.MAX_VALUE分离队列中两遍处理的顶点，变量N 记录操作了几遍，当N等于顶点个数时算法完成。算法最终广义树形式的SPT。以图为示例，起始顶点为顶点4,根据算法过程，SPT创建过程如图图中记录 每遍处理后各顶点的最短距离和队列中的顶点标号。图Bellman-Ford算法的示例图0 1 2 3 4 5D8 8 8 8 0 8a012 3 4 sD|8|8|32|36|0|8|bI。I 5 I 80 1 2 3 4 5|81|122|32|36|0|-2|最终得到的SPT为:图Bliman ford算法求解得至IJ的SPT 以图作为示例，编写算法示例程序：电Ipublic class BellmanFordExample public static void main(String args)GraphLnk GL=Utilities.BulidGraphLnkFromFile(Graph、graph10.txt);MinusWeightGraph MWG=new MinusWeightGraph(GL);MWG.BellmanFord(4);System.out.printin();MWG.mst.ford_print_tree();)程序运行结果为：队列的元素项从列首到列尾为:4,2147483647.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为:2147483647,2,3.O队列的元素项从列首到列尾为:3,2147483647.队列的元素项从列首到列尾为:3,2147483647.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为：2147483647,0,5.O队列的元素项从列首到列尾为：5,2147483647.队列的元素项从列首到列尾为:5,2147483647,1.。队列的元素项从列首到列尾为:2147483647,1.队列的元素项从列首到列尾为:2147483647,1,1.。队列的元素项从列首到列尾为:1,2147483647.队列的元素项从列首到列尾为:1,2147483647,2.O队列的元素项从列首到列尾为:2147483647,2.队列的元素项从列首到列尾为:2147483647,2.O队列的元素项从列首到列尾为:2147483647.队列的元素项从列首到列尾为:2147483647.。队列为空6节点，前序遍历打印：|-0.0(4)|-36.0(3)|-2.0(5)I-31.0(1)I-20.0(2)I-81.0(0)3全源最短路径本节中我们将讨论全源最短路径问题。可以简单地认为全源最短路径问题是单源最短路 径问题的推广，即分别以每个顶点作为起始顶点，求其其余顶点到起始顶点的最短距离。例 如，在有向非负权值图的中，将每个顶点作为起始顶点，利用Dijkstra算法求解其余顶点 到起始顶点的最短距离，算法的时间开销为VE/gV。这里我们将讨论的两种算法针对更为一般的图，图中各条边的权值可以为负数。第一种 算法为Floyd算法，针对稠密图，时间开销为V；第二种算法为Johnson算法，针对稀疏图，该算法结合单源最短路径算法Bellman-Ford算法和Dijkstra算法，算法时间开销为 VE/ogdV。两种算法求解的都是权值可以为负数(不包含负环)的有向带权图。3.1 Floyd 算法Floyd算法比较简单，通过检查每条边的距离来确定该边是否为一条更短路径的一部 分。算法实现如下：小public class AllPairsShortestPaths/待处理的图GraphLnk G;/Vi j表示i在生成树中的父节点EdgeElem P;/Di表示Vi与i形成的边的权值double D;/构造函数public AllPairsShortestPaths(GraphLnk G)this.G=G;/根据G的节点数创建数组int V=G.get_nv();D=new doubleVV;/初始化for(int i=0;i V;i+)for(int j=0;j V;j+)Dij=Double.MAX_VALUE;P=new EdgeElemVV;for(int i=0;i V;i+)for(int j=0;j V;j+)if(G.isEdge(if j)/将连接边添加到P数组中，更新D数组Pij=new EdgeElem(new EdgeLnk(i,j,null)rG.getEdgeWt(if j);Dij=G.getEdgeWt(if j);)/数组D对角元设为0for(int i=0;i V;i+)Di i=0.0;/打印中间结果for(int i=0;i D.length;i+)for(int j=0;j D.length;j+)if(Dij!=Double.MAX_VALUE)System.out.print(D i j+ntn);else System.out.print(000t);)System.out.printIn();)System.out.printin(n n-)/*夫Floyd算法，求解全部最短路径算法O(V入3);大函数没有入参。public void Floyd()int V=G.get_nv();for(int i=0;i V;i+)for(int j=0;j V;j+)if(Pji!=null)for(int t=0;t D j i+Di t)P j t=P j i;D j t=D j i+Di t;/打印中间结果for(int i2=0;i2 D.length;i2+)for(int j2=0;j2 D.length;j2+)if(Di2 j2!=Double.MAX_VALUE)System.out.print(D12j2+nt);else System.out.print(000t);)System.out.printIn();)System,out.println(nn-);)电算法通过三重循环实现每对顶点之间的最短路径，如图，对顶点每个i,松弛每条边(j,t),检查它的距离并确定是否存在更短的路径，并且边(j,i)为该路径中的边。算法实现过 程中打印显示i变化过程中每对顶点之间的最短距离。算法时间开销与V，成正比。算法中用二维数组D存放每对顶点之间的最短距离，例如，表示顶点i到顶点j之间的最短距离；数组P存放顶点顶点的路径，例如，表示顶点i到顶点j之间最短路径中的第一条表，按图索骥可以找到顶点i到j之间最短路 径上的每条边。图Floyd算法三重循环松弛操作以图(负权图)为示例，编写Floyd算法 测试示例程序：电public class FloydExample public static void main(String args)GraphLnk GL=Utilities.BulidGraphLnkFromFile(Graphgraph10.txt);AllPairsShortestPaths APSP=new AllPairsShortestPaths(GL);APSP.Floyd();System.out.print In(n 各顶点最短路径：);for(int i=0;i APSP.D.length;i+)for(int j=0;j”+APSP.Pij.get_v2()+t);elseSystem.out.print(-t);)System.out.printin();程序运行结果如下:0 418 0OO 845 88 OO00 2 9=0=0 418 0OO OO45 86OO OO00 2 90 418 0OO OO45 86OO OO00 2 951 80 508 032 368 2932 8OO OO8-380 8OO OO 21 0OO OO OO 2 951 8 32 80 50 oo co8 o 8-3832 36 c)88 8 21 092 8 73 2951 00 32 000 50 oo oo137 0 118-3832 36 c)822 oo 3 02041921427329OO051101328OOOO050 50 5 0 5 0 5 0 51 4-1 2 1 4 1 4 1 42 3 2 3-2 3 2 3 2 330 353 5-3 5 3 543 434 3 4 3-4 35 1 5 15 1 5 1 5 1-结果第一部分为算法过程中记录的每对顶点之间的最短距离，用二维数组的形式返回；第二部分为每对顶点之间最短路径。例如，顶点0到顶点2之间的最短路径，首先取边(0,5)；然后需要寻找顶点5到顶点2之间最短路径，取边(5,4)；然后需要寻找顶点4到顶点2之间最 短路径，取边(4,2),到达顶点2,所以顶点0到顶点2之间的最短路径为v。，v5,V4,v2,我们可以计算这条路径的长度为二(0,5)+3(5,4)+3(4,2)=29+21+32=82,与距离矩阵 D02相等。3.2 Johnson 算法Johnson算法可以在0(VE/gV)时间内求解每对顶点之间的最短路径。对于稀疏图，该算 法在要好于Floyd算法。算法与Floyd算法类似，每对顶点之间的最短距离用二维数组D 表示；如果图中存在负环，算法将输出警告信息。Johnson算法把Bellman-Ford算法和 Dijkstra算法作为其子函数。在本节一开始我们提到，如果以每个顶点作为起始顶点，用Dijkstra算法求解单源最 短路径，则可以求解全源最短路径，算法复杂度为VE/gV。但是对含有负权值的图，Dijkstra 算法将失效。Johnson算法运用了“重赋权”技术，即将原图中每条边的权值,重新赋值 为s,并且具有以下两个性质：对所有顶点对U,v,路径P是以权值为3的原图的最短路径，当且仅当路径P也是 以权值为3的图的最短路径；,对于所有的边(U,V),3(U,V)是非负数。重赋权后的图可以利用Dijkstra算法求解任意两个顶点之间的最短路径。稍后我们将 会看到，重赋值不会改变最短路径，其处理复杂度为0(VE)。下面我们将构造运算使得重赋权操作后得到的新的权值s满足上面提及的两个性 质。对带权有向图G二(V,E),边(u,v)的权值s(u,v),设h为顶点映射到实数域的映 射函数。对图中每条边(u,V),定义：s(U,V)=3(u,V)+h(u)-h(v)在这样的构造运算可以满足第一条性质，即如果路径pXv。，Vk是权值3条件下 顶点V。到Vk的最短路径，那么p也是新权值3条件下的最短路径。用len/p)表示路径p 在原图中的长度，len-(p)表示路径p在重赋权后的图中的长度，则lerw(p)=s(vo,vi)+s(vi,V2)+co(vi,Vk)=5(vo,vi)+h(vo)-h(vi)+s(vi,v2)+h(vi)-h(v2)+co(vi,Vk)+h(Vk-i)-h(vk)=3(Vo,Vi)+3(Vi,V2)+3(Vk-l,Vk)+h(vo)-h(vk)=lenu(p)+h(vo)-h(vk)所以，如果权值为3条件下顶点v。到Vk存在一条更短的路径P*,那么对应地，在以权 值为3的条件下，路径P*也比路径p更短。再考虑第二条性质，即保证重赋权后权值非负。我们做如下的构造运算：对给定的图G=(V,E),边(u,V)的权值3(u,V),构造一个新的图G=(V,E),其中一个新的顶点 sV,V?=VU s,E=EU(s,u):ue V,对所有的 uV,s(s,u)=0o G中没有以顶点s为终点的边，所以，如果G中不存在负环，那么中也 不会存在负环。在不存在负环的前提下，定义h(u)=lenmin(s,u),即顶点S到顶点u的最短路径，那么 对所有的边(V,u)ev,h(u)w h(v)+3(v,u)o 那么在 h(u)=lerimin(s,u)的条件下，便可满足3,(U,V)二3(U,V)+h(U)-h(V)m0,这样第二条性质便可满足。在 上一节中我们讨论的Bellman-Ford算法能求解无负环的单元最短路径问题，可以用于求解 h函数，其算法复杂度为0(VE)。根据上面的讨论，Johnson算法结合Bellman-Ford算法和Di jkstra算法，包括以下几 个步骤：,构造原图的扩展图G二(V,E),V=VUs,E=EU(s,u):ue v；,在G，中以s为起始顶点应用Bellman-Ford算法，求解各顶点到顶点s的最短路径；对原图重赋权；重赋权后以图中每个顶点为起始顶点，应用Dijkstra算法求解每对顶点之间的最 短路径；由于重赋权改变了图中路径的长度，最后需要还原上一步骤中求得最短路径的长 度；根据以上步骤，算法的实现如下：public class JohnsonAlgo double D;int P;GraphLnk G;/*夫构造函数*/public JohnsonAlgo(GraphLnk G)this.G=G;D=new doubleG.get_nv()G.get_nv();P=new intG.get_nv()G.get_nv();)public boolean Johnson()/创建一个图_GGraphLnk _G=new GraphLnk(G.get_nv()+1);for(int i=0;i G.get_nv();i+)for(Edge e=G.firstEdge(i);G.isEdge(e);e=G.nextEdge(e)_G.setEdgeWt(e.get_vl(),e.get_v2(),G.getEdgeWt(e);)/在原图的基础上添加一个顶点adint ad=_G.get_nv()-1;for(int i=0;i G.get_nv();i+)_G.setEdgeWt(adf i,0);)/首先调用Bellman-Ford算法，以ad为起始点MinusWeightGraph swg=new MinusWeightGraph(_G);swg.BellmanFord(ad);/h函数int h=new intG.get_nv()+1;Systm.out.printin(Bliman-Ford 算法结果：);for(int i=0;i _G.get_nv();i+)System.out.print(hi=(int)swg.Di)+nt);System.out.printin();for(int i=0;i he.get_vl()+_G.getEdgeWt(e)(System.out.printin(“图中有负环。);return false;)/如果没有则重赋权else int u=G.edge_vl(e)f v=G.edge_v2(e);int wt=(int)(G.getEdgeWt(e)+hG.edge_vl(e)-hG.edge_v2(e);G.setEdgeWt(uf v,wt);)System.out.printIn(重赋权后的各条边的权值：);for(int u=0;u G.get_nv();u+)for(Edge e=G.firstEdge(u);G.isEdge(e);e=G.nextEdge(e)System.out.print(u+e.get_v2()+“+G.getEdgeWt(e)+tn);)System.out.printin();)/Dijkstra算法求解每一个顶点的最短路径树SingleSourceShortestPaths sssp=new SinglesourceShortestPaths(G);for(int i=0;i G.get_nv();i+)sssp.Dijkstra(i);System,out.print In(n n+i+顶点 Di jkstra 结果：);for(int j=0;j G.get_nv();j+)System.out.print(sssp.Dj+t);D i j=sssp.Dj+hj-hi;P i j=sssp.Vj;)System.out.printin();return true;根据算法描述步骤和实现代码，以图为例，算法的具体过程如图(ai)：Bellman-Ford算法求解得到各个顶点的最短路径的长度对应这顶点的h函数的映射值,分别为：h(0)=0,h(1)=-67,h(2)=-16,h(3)=0,h(4)=-35,h(5)=38,h(6)=0.接下来根据各顶点的h函数值对原图G进行重赋权操作：s(u,V)=3(u,V)+h(u)-h(v)过程为：3(0,1)=(41)+(0)-(-67)=108s (0,5)s 1 d0以图为例，编写算法程序的示例：public class JohnsonExample public static void main(String args)GraphLnk g_minus=Utilities.BulidGraphLnkFromFile(Graph、graph10.txt);JohnsonAlgo ja=new JohnsonAlgo(g_minus);ja.Johnson();System.out.printIn(每对顶点之间的最短路径长度：”);for(int i=0;i g_minus.get_nv();i+)for(int j=0;j g_minus.get_nv();j+)System.out.print(int)ja.Dij+nt);)System.out.printin();)System.out.printIn(每对顶点之间的最短路径：);for(int i=0;i g_minus.get_nv();i+)for(int j=0;j g_minus.get_nv();j+)System.out.print(ja.Pi j+nt);)System.out.printIn();)程序运行部分结果如下：Bellman-Ford 算法结果：0-67-16 0-35-38 07节点，前序遍历打印：I-0.0(6)I-0.0(0)I-0.0(3)|-38.0(5)|-67.0(1)I-16.0(2)|-35.0(4)重赋权后的各条边的权值：0-1 108 0-5 671-2 0 1-4 02-3 343-0 45 3-5 04-2 13 4-3 15-1 0 5-4 18第0顶点Dijkstra结果：0.0 67.0 67.0 68.0 67.0 67.06节点，前序遍历打印：|-0.0(0)|-67.0(5)|-67.0(1)|-67.0(2)I-67.0(4)|-68.0(3)第1顶点Dijkstra结果：46.0 0.0 0.0 1.0 0.0 1.06节点，前序遍历打印：I0.0(1)|-0.0(2)|-0.0(4)I1.0(3)I1.0(5)|-4 6.0(0)第2顶点Dijkstra结果：79.0 34.0 0.0 34.0 34.0 34.06节点，前序遍历打印：|-0.0(2)|-34.0(3)I-34.0(5)I-34.0(1)I-34.0(4)|-79.0(0)第3顶点Dijkstra结果：45.0 0.0 0.0 0.0 0.0 0.06节点，前序遍历打印：|-0.0(3)|-45.0(0)|-0.0(5)I0.0(1)|-0.0(2)|-0.0(4)第4顶点Dijkstra结果：46.0 1.0 1.0 1.0 0.0 1.06节点，前序遍历打印：|-0.0(4)I1.0(3)I1.0(5)I1.0(1)I1.0(2)I-46.0(0)第5顶点Dijkstra结果：46.0 0.0 0.0 1.0 0.0 0.06节点，前序遍历打印：|-0.0(5)I0.0(1)|-0.0(2)|-0.0(4)I1.0(3)|-46.0(0)每对顶点之间的最短路径长度:0 0 51113 095-1745-6781-3184-2968 3251 680 50-16 020 3622 392932 3015 12-35-380-23 0每对顶点之间的最短路径:-15 13-113 5-13 5 13 5 13 5 14 104 132 13-1134-134 1-1结果每个部分分别对应着算法中的各个步骤,读者可以结合算法步骤以及上面分析的算 法过程对结果做进一步理解。