精选优质文档-倾情为你奉上实验五 分支限界法实现单源最短路径一 实验题目：分支限界法实现单源最短路径问题二 实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。三 实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。四 实验代码#includeusing namespace std;const int size = 100;const int inf = 5000; /两点距离上界const int n = 6; /图顶点个数加1int
