通信网理论基础（虞红芳）研究型project实验报告

《通信网理论基础（虞红芳）研究型project实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、研究型project实验报告1.问题描述对比/定量研究Dijkstra算法和双向Dijkstra算法的性能。两种算法使用相同的数据结构以及相同的随机图生成算法。2.求解方法1.实验条件：相同的数据结构相同的随机图牛成算法相同的邻接矩阵使用毫秒级时间测量函数对两个函数的时间进行计算150个节点的描述分别使用稀疏图和稠密图进行对比2.双向算法描述：在单向描述算法从源点发起寻找的基础上，利用后继节点作为反向搜索算法的前驱节点，然后合并正向以及逆向的寻找结果。3•时间对比方法：引入两个时间对比。第一个是总体时间，

2、即在对150个随机图进行测试后，记录每一次的时间，然后比较运行了150次后总体速度谁快谁慢；第二个是次数比较，即在对150个随机图进行测试的过程中，每一次都比较谁快，然后记录，最后比较谁快的次数比较多，谁就更快。3•代码描述：1・邻接矩阵生成算法：voidCGraph::graph_adj(){intresize_num=numVertex+5;set::iteratoritvlritv2;//动态利用点的数量生成二维向虽//vector>adj_grap

3、h;//遍历边，然后进行计算list::iteratoriter;//CEdge*empty_edge=newCEdge(0,0,0,INFINITY);//遍历vector,初始化为NULL；cout<<*obj_vertex•:rbegin()«endl;itvl=obj_vertex.end();itvl——;j_graph.resize((*itvl)+5,vector((*itvl)+5));resize_num=adj_graph.size();maxnumbe

4、r=resize_num;for(itvl=obj_vertex・begin();itvl!=obj_vertex.end();itvl++){for(itv2=obj_vertex.begin();itv2!=obj_vertex.end();itv2++)adj_graph[(*itvl)][(*itv2)]=empty_edge;}2•单向迪杰斯特拉算法描述：voidCGraph::Dijkstra(intchoice,vector>adj_graph_temp){in

5、tinput_src,input_dst;"输入原、宿点*7input_dst=*(obj_vertex•rbegin());input_src=*(obj_vertex.begin());/*根据源点初始化*///创建CPath对象//CPath::CPath(intvertex_nunbintsource,intdestination,setver_set)CPath*Dij_path=newCPmth(CGraph::numVertex,input_srczinput_dst,obj_ve

6、rtexrmaxnumber);//1S_KNOWN[i]==1表示己经放到了己知最短路径节点集合中vectorIS_KNOWN;IS_KNOWN.resize(maxnumber+5);set::iteratorit_set,it_findmin;for(it_set=obj_vertQX・begin();it_set!=obj_vertQx.end();it_set++){//全部设置为未访问IS_KNOWN[(*it_set)]=0;//利用邻接矩阵进行初始化，如果为N

7、ULL,则保持其距离为无穷大，若不为零，贝0调用函数赋值，并把其前驱节点设置为input.srcif(NULL!=adj_graph_temp[input_src][(*it_set)]){//取得相应节点的pair：(*(*Dij_path).Get_Pair((*it_set)))(*(*Dij_path)・Get_Pair((*it_set)))・second=(*adj_graph_temp[input_src][(*it_set)])・GetEdgeWeight();(*(*Dij_path).

8、Get_Pair((*it_set)))・first=input_src;}}//把源点初始化，排除在循环以外(*(*Dij_path).Get_Pair(input_src)).second=0;IS_KNOWN[input_src-1]=1;"主循环，每次求得一个点的最短路径，记得添加对宿点的判断★//*在主循环中，先是寻找目前最近的点*/"把目前最近的点放进永久final,并检査是不是宿点*/"修正冃前所有的最短路径*/