清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 2.算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存 储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的 U子结点被依次插入堆中。此后,算法从堆中取出具有最小当前 路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点倒顶点有边可达,且从源出 发,途经顶点再到顶忘的所相应的路径的长度小于当前最优路 径长度,则将该页点作为活结点插入到活结点优先队列中。这个 结点的扩展过程一直继续到活结点优先队列为空时为止。8 6.2 单源最短路径问题 2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存 储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的 儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前 路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出 发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路 径长度，则将该顶点作为活结点插入到活结点优先队列中。这个 结点的扩展过程一直继续到活结点优先队列为空时为止