《算法单源最短路径问题.ppt》由会员分享，可在线阅读，更多相关《算法单源最短路径问题.ppt（5页珍藏版）》请在三一办公上搜索。
1、1,6.2单源最短路径问题,1.问题描述,下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,2,6.2单源最短路径问题,1.问题描述,下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,3,6.2单源最短路径问题,2.算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小
2、当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,4,6.2单源最短路径问题,3.剪枝策略,在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,5,6.2单源最短路径问题,while(true)for(int j=1;j N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E);/取下一扩展结点 catch(OutOfBounds)break;/优先队列空,顶点I和j间有边，且此路径长小于原先从原点到j的路径长,
