§2 最短路问题 ◆最短路问题：对一个赋权的有向图D中的指定的两个点V。和V:找到 一条从V到的路，使这条路上所有孤弧的权数的总和最小，这条路被 称之为从V到V,的最短路。这条路上所有孤的权数的总和被称为从V 到V的距离。 ◆求解最短路的Dijkstra算法（双标号法) ◆步骤： 1.给出点V1以标号(0，S) 2.找出已标号的点的集合I,没标号的点的集合J及孤的集合 {(%,V)I∈1，V∈J} 3.如果上述孤的集合是空集，则计算结束。如果V,已标号(，k),则V。到 M的距离为，而从V到V:的最短路径，则可以从V反向追踪到起点 Vs而得到。如果V:未标号，则可以断言不存在从V。到V的有向路。 如果上述的孤的集合不是空集，则转下一步。 4.对上述孤的集合中的每一条孤，计算S=+C0在所有的S中，找 到其值为最小的孤。不妨设此孤为(V),则给此孤的终点以双标号 (Sca,C),返回步骤2。11.2 最短路问题 u 最短路问题：对一个赋权的有向图 D 中的指定的两个点 vs 和 vt 找到 一条从 vs 到vt 的路，使这条路上所有弧的权数的总和最小，这条路被 称之为从 vs 到 vt 的最短路。这条路上所有弧的权数的总和被称为从 vs 到 vt 的距离。 u 求解最短路的 Dijkstra 算法（双标号法） u 步骤： 1．给出点 v1 以标号（0,s） 2．找出已标号的点的集合 I，没标号的点的集合 J 及弧的集合 {(vi , v j ) | vi ∈ I , v j ∈ J } 3．如果上述弧的集合是空集，则计算结束。如果 vt 已标号(l t,kt)，则 vs 到 vt 的距离为 l t，而从 vs 到 vt 的最短路径，则可以从 vt 反向追踪到起点 vs 而得到。如果 vt 未标号，则可以断言不存在从 vs 到 vt 的有向路。 如果上述的弧的集合不是空集，则转下一步。 4．对上述弧的集合中的每一条弧，计算 sij = l i + cij。在所有的 sij 中，找 到其值为最小的弧。不妨设此弧为(vc ,vd )，则给此弧的终点以双标号 (scd ,c)，返回步骤 2。 § 2