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

1、实验五 分支限界法实现单源最短路径一 实验题目：分支限界法实现单源最短路径问题二 实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。三 实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

2、这个结点的扩展过程一直继续到活结点优先队列为空时为止。四 实验代码#includeusing namespace std;const int size = 100;const int inf = 5000; /两点距离上界const int n = 6; /图顶点个数加1int prevn; /图的前驱顶点int dist = 0,0,5000,5000,5000,5000; /最短距离数组int cnn = 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,

3、0,2,0,5000,5000,5000,5000,0;const int n = 5; /图顶点个数加1int prevn; /图的前驱顶点int dist = 0,0,5000,5000,5000;int cn = 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 MinHeapNodepublic : int i; /顶点编号 int length; /当前路长;/循环队列class CirQueueprivate: int front,rear; MinHeapNode datasi

4、ze;public: CirQueue() front = rear = 0; /元素入队操作 void queryIn(MinHeapNode e) if(rear +1)%size != front) rear = (rear+1)%size; /队尾指针在循环意义下加1 datarear = e; /在队尾插入元素 /元素出队操作 MinHeapNode queryOut() if(rear != front) front = (front+1)%size; /队列在循环意义下加1 return datafront; /读取队头元素，但不出队 MinHeapNode getQuery()

5、 if(rear != front) return data(front+1)%size; /判断队列是否为空bool empty() return front = rear; /判断队列是否为满bool full() return (rear +1)%size = front; ;/CirQueue结束class Graphpublic: /* * 单源最短路径问题的优先队列式分支限界法 */ void shortestPath(int v) CirQueue qq;/定义源为初始扩展结点 MinHeapNode e; e.i = v; e.length = 0; distv = 0; qq

6、.queryIn(e); /搜索问题的解空间 while(true) for(int j = 1;j=n) break; MinHeapNode m = qq.getQuery();if(cm.ijinf)&(m.length + cm.ij distj) /顶点i到顶点j可达，且满足控制约束 distj = m.length + cm.ij; prevj = m.i; /加入活结点优先队列 MinHeapNode mi; mi.i = j; mi.length = distj; if(qq.full() break; qq.queryIn(mi); /元素入队 /for循环结束 if(qq.empty() break; qq.queryOut(); /当该结点的孩子结点全部入队后，删除该结点 /while循环结束 /方法结束;/类结束int main() Graph g; g.shortestPath(1); cout最短路径长为 distn-1endl; cout中间路径为： ; for(