资源描述：
《单源最短路径1 分支限界》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、实验名称：单源最短路径问题 时间：X年X月X日，星期3，第三、四节 地点：0#601 二、实验目的及要求 1、掌握分支限界法解题步骤： 1在问题的边带权的解空间树中进行广度优先搜索 2找一个叶结点使其对应路径的权最小(最大) 3当搜索到达一个扩展结点时,一次性扩展它的所有儿子 4将满足约束条件且最小耗费函数£目标函数限界的儿子,插入活结点 表中 5从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表 为空为止 三、实验环境 Window下的vs2010 四、实验内容 单源最短路径问题 以一个例子来说明单源最短路径问题：在下图所给的有向图G
2、中，每一边都有一个非负边权。 求图G的从源顶点s到目标顶点t之间的最短路径 五、算法描述及实验步骤 算法思想：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 结点扩展过程一直继续到
3、活结点优先队列为空时为止二．单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当
4、前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去
5、。 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。三．程序设计：#includeusingnamespacestd;constintsize=100;constintinf=5000;//两点距离上界//第一组测试参数constintn=6;//图顶点个数加1intprev[n];//图的前驱顶点intdist[]={0,0,5000,5000,5000,5000};//最短距离数组intc[n][n]={{0,0,0,0,0,0},{0,0,2,3,5000,5000},//图的邻接矩阵{0,50
6、00,0,1,2,5000},{0,5000,5000,0,9,2},{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};/*第二组测试参数constintn=5;//图顶点个数加1intprev[n];//图的前驱顶点intdist[]={0,0,5000,5000,5000};intc[][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0}};*/classMinHeapNode{publi
7、c:inti;//顶点编号intlength;//当前路长};//循环队列classCirQueue{private:intfront,rear;MinHeapNodedata[size];public:CirQueue(){front=rear=0;}//元素入队操作voidqueryIn(MinHeapNodee){if((rear+1)%size!=front){rear=(rear+1)%size;//队尾指针在循环意义下加1data[rear]=e;//在队尾插入元素}}//元素出队操作MinHeapNodequeryOut(){if(rear!=
8、front){front=(front+1)%siz
