§2最短路问题 最短路问题:对一个赋权的有向图D中的指定的两个点V和V找到一条 从v到的路,使得这条路上所有弧的权数的总和最小,这条路被称 之为从V到V的最短路。这条路上所有弧的权数的总和被称为从到v 的距离。 、求解最短路的 Dijkstra算法(双标号法) 步骤: 1给出点V以标号(0,s) 2找出已标号的点的集合I,没标号的点的集合J以及弧的集合 (,v)v∈1,V∈ 3.如果上述弧的集合是空集,则计算结束。如果v已标号(Lnk),则v 到v的距离为1,而从ⅴ到v的最短路径,则可以从k反向追踪到起点 v而得到。如果v未标号,则可以断言不存在从v到v的有向路。如果 上述的弧的集合不是空集,则转下一步 4.对上述弧的集合中的每一条弧,计算s=-+ci。在所有的s中,找到其 值为最小的弧。不妨设此弧为(VV),则给此弧的终点以双标号 (sa,c),返回步骤2。管 理 运 筹 学 7 §2 最短路问题 • 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条 从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称 之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt 的距离。 一、求解最短路的Dijkstra算法(双标号法） 步骤： 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合 3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（l t ,kt），则vs 到vt的距离为l t，而从vs到vt的最短路径，则可以从kt 反向追踪到起点 vs 而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果 上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算sij=li+cij 。在所有的sij中，找到其 值为最小的弧。不妨设此弧为（Vc ,Vd），则给此弧的终点以双标号 （scd,c）,返回步骤2。 {( , ) | , } i j i j v v v I v J  