最短路径与关键路径.docVIP

第四节最短路径与关键路径 1．最短路径：对于图 G＝V, E(有向图或无向图 )的每一条边 e都附加一个实数 w(e)，w(e)称为 e的权，则称 G是一个带权图或赋权图，并把它记作 G＝V , E, w ， 其中w是 E上的实函数，叫作权函数。对于简单图，当 e =(vi ,vj )（或vi ,vj ），常把w(e) 记作wij。 设 G＝V , E, w 是n阶简单带权图（无向的或有向的），边（vi ,vj）（或vi ,vj ） 的权为wij，并且约定：wii = 0;当 vi与vj之间无边关联时 wij＝∞。G中一条通路（回 路）上各条边的权之和叫作该通路（回路）的权。G中从vi到vj的权最小的通路叫作 vi到 vj的最短路径。根据刚才的约定，若不存在从 vi到vj的通路，则认为vi到vj的最短路径 的权为∞。所谓最短路径问题就是求给定图中两点之间的最短路径。 下面介绍求最短路径问题的 Dijkstra标号法。它仅可用于所有的权wij ≥ 0的情况，可 以求从给定顶点（设为v1）到所有顶点的最短路径。先介绍几个符号和名词。 （1）设li(r)?为顶点v1（最短路径的起点）到vi（最短路径的终点）的最短路径的权。 若vi获得 l i(r)?，称vi在第r(r ≥ 0)步获得了永久性标号，简称为 p标号。由于v1为起点， 且w＝0，故当r = 0时，l1(0)? = 0，首先v1获得永久性标号 P。 11 （2）设l(jr)为 v1到vj的最短路径的权在第r步获得的一个上界，称l(jr)为顶点vj的 临时性标号，简称t标号，其中，r ≥ 0，开始的时候，l j = w1j。 (0) （3）设Pr = {v v在前r步获 p标号}，称 Pr为第 r步的通过集，r ≥ 0。 （4）设Tr =V ? Pr，称Tr为第r步未通过集。 Dijkstra标号法的计算步骤如下： （1 ）开始 令r ← 0，获 p标号：l1(0)? = 0,P0 ={v1},T0 =V ? P0,vj( j ≠1)的t标号为l(0)j = w1j （2）求下一个 p标号顶点。 令r ← r +1。设 min{l(jr?1)}＝li(r?1)，则记li(r)? = li(r?1)，将li(r)?放在相应顶点vi处， v ∈T j r?1 表明vi获 p标号。修改通过集和未通过集：令 Pr = Pr?1U{vi},Tr =Tr?1 ?{vi} 检查 Tr。若Tr = ?，则算法结束，否则执行（3）。 (3)修改Tr中各顶点的 t标号。 令 l (jr) = min{l(jr?1),li(r)? + wij},vj ∈Tr。 转（2）。 例 4.1 求图 4.1中 v1到其余顶点的最短路径及其权。 解用 Dijkstra标号法求解计算过程如表 4.1所示。 T0 ={v2,v3,v4},这里 （1）r =1： l ,l3 ,l }= min{3,1,∞}=1= l3 3(1)? = min{l2(0) (0) (0) (0) ,l3(1)?的下标之所以取作 3，是因为最 4 小值是在第三个顶点处取得。 v3在第一步获 P标号（永久性标号），v1到v3的最短路 ，因此 v1到 v3的最短路径就是边 v1,v3 。这样 T1 =T0 ?{v3}={v2,v4}，这两个顶点的临时性标号（T标号）为 径的权为 l 3(1)?＝1 l l (1) 2 = min{l2 (0) ,l3(1)? + w32}= min{3,1,+3}= 3 (1) 4 = min{l4 (0) ,l3(1)? + w34}= min{∞,1,+5}= 6。 （2）r = 2： min{l2 (1) ,l }= min{3,6}= 3 = l2 (1) (1) = l2(2)?，v2在第二步获得永久性标号 P, v1到v2的 4 最短路径的权就是 3，因此v1到v2的最短路径就是边 v1,v2。这样T2 ={v4}，v4的临时性 标号为 l (2) 4 = min{l4 (1),l2(2)? + w24}= min{6,3+ 2}= 5。 （3）r = 3： 4(3)? = min{