限界核查报告什么时候出具.docVIP

限界核查报告什么时候出具 分枝限界法_实验报告 一、课题名称 用分枝限界法求解单源最短路径问题 二、课题内容和要求 设计要求：学习算法设计中分枝限界法的思想，设计算法解决数据结构中求解单源最短路径问题，编程实现： （1）给出指定源点的单源最短路径； （2）说明算法的时间复杂度。 三、需求分析 1.实现极小堆的创建，用来存储活结点表。 2.实现循环队列的创建、初始化、入队、出队等操作。 3.实现分支限界法来实现求解单元最短路径的算法。 4.实现最短路径的正确输出。 四、概要设计 建立工程MinPath.dsw,加入源文件main.cpp，头文件CirQueue.h,init.h，Minpath.h和output.h. CirQueue.h中实现极小堆的创建，循环队列的创建、初始化、入队、出队等操作，Minpath.h中实现分支限界法来实现求解单元最短路径的算法。output.h中实现最短路径的正确输出。如下图所示： 实验用例如下，通过邻接矩阵的方式写在init.h中： 五、详细设计 main函数： #includeiostream.h #includeinit.h #includeCirQueue.h #includeMinPath.h #includeoutput.h void main() { int k; int q; cout------------欢迎使用本系统---------------endl; cout------------请选择单元路径的起点：---------------endl; cout------------提示：输入1到n-1之间的整数---------------endl; cink; cout------------请选择单元路径的终点：---------------endl; cinq; while(k1||k11) { cout------------提示：输入1到n-1之间的数，请重新输入---------------endl; } cink; MinPath(k); } init.h output(k,q); const int size = 200; const int inf = 1000;//两点距离上界置为1000 const int n = 12; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf}; //最短距离数组 int c[n][n] = {{0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,2,3,4,inf,inf,inf,inf,inf,inf,inf}, {0,inf,0,3,inf,7,2,inf,inf,inf,inf,inf}, {0,inf,inf,0,inf,inf,9,2,inf,inf,inf,inf}, {0,inf,inf,inf,0,inf,inf,2,inf,inf,inf,inf}, {0,inf,inf,inf,inf,0,inf,inf,3,3,inf,inf}, {0,inf,inf,inf,inf,inf,0,1,inf,3,inf,inf}, {0,inf,inf,inf,inf,inf,inf,0,inf,5,1,inf}, {0,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,3}, {0,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,2}, {0,inf,inf,inf,inf,inf,inf,inf,inf,2,inf,2}, {0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0},}; //矩阵 CirQueue.h 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; //插入新的队尾元素 data[rear] = e;//在队尾插入元素} } void queryOut()//元素出队操作 { if(rear != f