一、实验名称：单源最短路径问题 时间：X 年 X 月 X 日，星期 3，第三、四节 地点：0#601 二、实验目的及要求 1、掌握分支限界法解题步骤： 1 在问题的边带权的解空间树中进行广度优先搜索 2 找一个叶结点使其对应路径的权最小(最大) 3 当搜索到达一个扩展结点时,一次性扩展它的所有儿子 4 将满足约束条件且最小耗费函数目标函数限界的儿子,插入活结点 表中 5 从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表 为空为止 三、实验环境 Window 下的 vs2010 四、实验内容 单源最短路径问题 以一个例子来说明单源最短路径问题：在下图所给的有向图 G 中，每一边都有一个非负边权。 求图 G 的从源顶点 s 到目标顶点 t 之间的最短路径 五、算法描述及实验步骤 算法思想： 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图 G 的源顶点 s 和空优先队列开始。结点 s 被扩展后，它的儿子结点被依次插入堆中。 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点 i 到 j 有边可达，且从源出发，途经 i 再到 j 的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 结点扩展过程一直继续到活结点优先队列为空时为止 二．单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G 中，每一边都有一个非负边权。要求图G 的从源顶点 s 到目标顶点 t之间的最短路径。 下图是用优先队列式分支限界法解有向图G 的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。 2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G 的源顶点s 和空优先队列开始。结点s 被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i 到顶点j 有边可达，且从源出发，途经顶点i 再到顶点j 的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。 3. ...
