单源最短路径问题 2.算法思想 解单源最短路径问题的优先队列式分支限界法用一极小 堆来存储活结点表。其优先级是结点所对应的当前路长
16 单源最短路径问题 2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小 堆来存储活结点表。其优先级是结点所对应的当前路长
单源最短路径问题 2.算法思想 ˉ算法从图G的源顶点S和空优先队列开始。结点s被扩展后,它的 儿子结点被依次插入堆中。此后,算法从堆中取出具有最小当前 路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点到顶点有边可达,且从源出 发,途经顶点再到顶点的所相应的路径的长度小于当前最优路 径长度,则将该顶点作为活结点插入到活结点优先队列中 ■这个结点的扩展过程一直继续到活结点优先队列为空时为止
17 单源最短路径问题 2. 算法思想 ◼算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的 儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前 路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出 发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路 径长度，则将该顶点作为活结点插入到活结点优先队列中。 ◼这个结点的扩展过程一直继续到活结点优先队列为空时为止
单源最短路径问题 3.剪枝策略 在算法扩展结点的过程中,一旦发现一个结点的下界 不小于当前找到的最短路长,则算法剪去以该结点为根的 子树。 在算法中,利用结点间的控制关系进行剪枝。从源顶点s 出发,2条不同路径到达图G的同一顶点。由于两条路径的 路长不同,因此可以将路长长的路径所对应的树中的结点 为根的子树剪去
18 单源最短路径问题 3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界 不小于当前找到的最短路长，则算法剪去以该结点为根的 子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s 出发，2条不同路径到达图G的同一顶点。由于两条路径的 路长不同，因此可以将路长长的路径所对应的树中的结点 为根的子树剪去
单源最短路径问题 3.剪枝策略 下图是用优先队列式分支限界法解有向图G的 单源最短路径问题产生的解空间树的剪枝情况。 cA优于B,B可剪枝 经过不同 4 的路径到 达相同的 g yk 顶点 7×5 6○10 14 p 10 19
19 单源最短路径问题 3. 剪枝策略 下图是用优先队列式分支限界法解有向图G的 单源最短路径问题产生的解空间树的剪枝情况。 经过不同 的路径到 达相同的 顶点 A B A优于B，B可剪枝
单源最短路径问题 while(true) for (intj=1; j <=n; j++) if(CEi小<inf&&( Elength+c[E[] <dist){顶点到顶点河达,且满足控制约束 dist=.length+cE.iG] previ=E. 顶点浰间有边,且此路 ∥加入活结点优先队列 径长小于原先从源点到消 Min node<type>n 路径长 N length=dit小l H Insert(N); j try (HDeleteMin(E) ∥取下一扩展结点 catch( OutofBounds){ break,}∥优先队列空 20
20 单源最短路径问题 while (true) { for (int j = 1; j <= n; j++) if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])) {// 顶点i到顶点j可达，且满足控制约束 dist[j]=E.length+c[E.i][j]; prev[j]=E.i; // 加入活结点优先队列 MinHeapNode<Type> N; N.i=j; N.length=dist[j]; H.Insert(N);} try {H.DeleteMin(E);} // 取下一扩展结点 catch (OutOfBounds) {break;} // 优先队列空 }} 顶点i和j间有边，且此路 径长小于原先从源点到j的 路径长