分支限界法实现单源最短路径问题.doc

实验五 分支限界法实现单源最短路径 一 实验题目：分支限界法实现单源最短路径问题 二 实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三 实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四 实验代码 #includeiostream using namespace std; const int size = 100; const int inf = 5000; //两点距离上界 const int n = 6; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000,5000}; //最短距离数组 int c[n][n] = {{0,0,0,0,0,0},{0,0,2,3,5000,5000}, //图的邻接矩阵 {0,5000,0,1,2,5000},{0,5000,5000,0,9,2}, {0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}}; const int n = 5; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000}; int c[][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}}; class MinHeapNode { public : int i; //顶点编号 int length; //当前路长 };//循环队列 class CirQueue{ private: int front,rear; MinHeapNode data[size]; public: CirQueue(){ front = rear = 0; }//元素入队操作 void queryIn(MinHeapNode e){ if((rear +1)%size != front){ rear = (rear+1)%size; //队尾指针在循环意义下加1 data[rear] = e; //在队尾插入元素 } }//元素出队操作 MinHeapNode queryOut(){ if(rear != front){ front = (front+1)%size; //队列在循环意义下加1 return data[front]; } } //读取队头元素，但不出队 MinHeapNode getQuery(){ if(rear != front) { return data[(front+1)%size]; } } //判断队列是否为空 bool empty() { return front == rear; } //判断队列是否为满 bool full() { return (rear +1)%size == front; } };//CirQueue结束 class Graph{ public: /** * 单源最短路径问题的优先队列式分支限界法 */ void shortestPath(int v) { CirQueue qq;//定义源为初始扩展结点 MinHeapNode e; e.i = v; e.length = 0; dist[v] = 0; qq.queryIn(e); //有哪些信誉好的足球投注网站问题的解空间 while(true){ for(int j = 1;jn;j++) { if(j=n) { break; } MinHeapNode m = qq.getQuery(); if((c[m.i][j]inf)(m.length + c[m.i][j] dist[j])) { //顶点i到顶点