资源描述：
《分支限界法实现单源最短路径问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验五分支限界法实现单源最短路径一实验题目：分支限界法实现单源最短路径问题二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结
2、点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。四实验代码#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,5000,0,1,2,5000},{0,5000,5000,0
3、,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{public:inti;//顶点编号intlength;//当前路长};//循环队列classCirQu
4、eue{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!=front){front=(front+1)%size;//队列在循环意义下加1returndata[fro
5、nt];}}//读取队头元素，但不出队MinHeapNodegetQuery(){if(rear!=front){returndata[(front+1)%size];}}//判断队列是否为空boolempty(){returnfront==rear;}//判断队列是否为满boolfull(){return(rear+1)%size==front;}};//CirQueue结束classGraph{public:/***单源最短路径问题的优先队列式分支限界法*/voidshortestPath(intv){CirQueueqq;//定义源为初始扩展结点MinHeapNod
6、ee;e.i=v;e.length=0;dist[v]=0;qq.queryIn(e);//搜索问题的解空间while(true){for(intj=1;j=n){break;}MinHeapNodem=qq.getQuery();if((c[m.i][j]7、(qq.full()){break;}qq.queryIn(mi);//元素入队}}//for循环结束if(qq.empty()){break;}qq.queryOut();//当该结点的孩子结点全部入队后，删除该结点}//while循环结束}//方法结束};//类结束intmain(){Graphg;g.shortestPath(1);cout<<"最短路径长为"<
