《2022年单源最短路径 .pdf》由会员分享，可在线阅读，更多相关《2022年单源最短路径 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计实验报告第 7 次实验姓名学号班级时间12.26 上午地点四合院实验名称分支界限法求最短路径实验目的（ 1）掌握并运用分支限界法基本思想（ 2）运用分支限界法实现单源最短路径问题。实验原理给定下示有向图，利用分支限界法的思想，计算并输出其单源最短路径。实验步骤1 算法从图 G 的源顶点 s 和空优先队列开始。结点 s 被扩展后，它的儿子结点被依次插入堆中；2 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点；3 如果从当前扩展结点 i 到 j 有边可达， 且从源出发， 途经 i 再到 j 的所相应路径长度，小于当前最优路径长度，则将
2、该顶点作为活结点插入到活结点优先队列中；4 结点扩展过程一直继续到活结点优先队列为空时为止关键代码void shorest(int v) priority_queue heap; HeapNode enode(v,0); for(int i=1; i=n; i+) disti=MAX; distv=0;/搜索问题的解空间 while(1) for(int j=1; j=n; j+) if(aenode.ijMAX & 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页
3、 - - - - - - - - - enode.length+aenode.ijdistj)/顶点 I 到 J 是可达的，并且满足控制约束 distj=enode.length+aenode.ij; HeapNode node(j,distj); heap.push(node);/加入活节点优先队列 if(heap.empty() break;/优先队列为空 else enode=heap.top(); heap.pop(); 测试结果随机数产生图的权值：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
4、 - - - - 第 2 页，共 5 页 - - - - - - - - - 附录：完整代码#include #include #include using namespace std; #define MAX 9999/定义为无限大#define N 60 int n,distN,aNN; class HeapNode/最小堆来存储活节点表 public: 实验心得通过这次实验， 我回顾了分支界限法求解最短路径问题，在其中加入了舍伍德随机化取值过程，使数据分布更加均匀，让我熟悉了随机化算法，也让结果更加公平可靠。本次实验在书本有详细的算法，很容易实现了上面的图形，同时仿照了回溯算法中随机取值
5、产生权值的方法生成了一个图，并且通过改进， 实现了随机选择源点的方法进行求解最短路径。通过这次实验， 不仅掌握了分支界限算法，还掌握了随机产生一个图并计算其最短路径的算法，让我觉得收获颇大。实验得分助教签名名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - int i,length;/顶点编号，当前的路径长度 HeapNode() HeapNode(int ii,int l) i=ii; length=l; bool operato
6、r(const HeapNode& node)const return lengthnode.length; ; void shorest(int v) priority_queue heap; HeapNode enode(v,0); for(int i=1; i=n; i+) disti=MAX; distv=0;/搜索问题的解空间 while(1) for(int j=1; j=n; j+) if(aenode.ijMAX & enode.length+aenode.ijdistj)/顶点 I到 J 是可达的，并且满足控制约束 distj=enode.length+aenode.ij;
7、HeapNode node(j,distj); heap.push(node);/加入活节点优先队列 if(heap.empty() break;/优先队列为空 else enode=heap.top(); heap.pop(); int main () int v,i; coutn; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - coutv; for(int i=1; i=n; i+) for(int j=1; j50) a
8、ij=MAX; coutn路径： endl; for( i=1;in+1;i+) for(int j=1;jn+1;j+) coutaij ; coutendl; shorest(v); coutendl; for( i=2; in; i+) coutv 到 i 的最短路径为：distiendl; coutv到i 的最短路径为：distnendl; system(pause); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -