清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 3.剪枝策略 在算法扩展结点的过程中,一旦发现一个结点的下界不小于 当前找到的最短路长,则算法剪去以该结点为根的子树。 在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发 2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因 此可以将路长长的路径所对应的树中的结点为根的子树剪去。9 6.2 单源最短路径问题 3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于 当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发， 2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因 此可以将路长长的路径所对应的树中的结点为根的子树剪去