北邮通信网理论基础 实验三四报告.doc

《北邮通信网理论基础 实验三四报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、通信网理论基础实验三、实验四代码分析24班曹爽2013210640实验二：Floyd算法代码说明：首先输入顶点个数和边的个数(指有向边的个数，比如从1到2和从2到1是不一样的,算作两条有向边)，确定问题规模。之后输入各边起点、终点和权值，顶点名称默认为0、1、2……如从1到2的权值为3,则输入1［空格］2［空格］3［回车］。由于我采用的是有向图，因此从1到2和从2到1是不同的，需要输入两次。待所有起点、终点和权值都输入完毕之后，整个图就建立完毕了。我没有采用输入邻接矩阵的形式，是考虑到有些点对之间用•能没有边连接，此时即便用户输入一个很大的权值,也有可能被其他路

2、径的权值之和超过，造成结果岀错。并且如果邻接矩阵是一个稀疏矩阵,输入很多0也是不必要的。因此我采用起点、终点和权值逐个输入的方式，对于没有边连接的部分，全部赋值为INF(Oxfffffff),省去了逐个输入的麻烦。之后输入要查询的起点和终点，利用Floyd算法即可计算出最短路径的权值，并且打印出最短路径；如果起点和终点没有路径连通，则返回找不到对应路径。代码&注释：#include#defineINFOxfffffff〃设置INF作为没有边时的赋值〃根据顶点个数建立矩阵〃先将全部元素赋值为INFusingnamespacestd;int**d

3、ist,**path;intmain()intn,T;inti,j,k;inta，b,v;intstart,finish.temp;cout«”请输入顶点个数：”;cin>>n;dist二newint*[n];path二newint*[n];for(i=0;ivn;i++){dist[i]二newint[n];path[i]=newint[n];}for(i=0;i

4、入边的个数：”；cin»T;cout«"请输入各边起点、终点与权值：(顶点名称默认为0,1,,"«n-l«")''«endl;while(T>0){cin>>a»b»v;dist⑻[b]=v;〃根据有向边的个数和用户输入来设置权值}for(i=0;idist[i][k]

5、+dist[k]U]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k];}}}}cout«"请输入要查询的起点和终点：”；cin>>start»finish;if(dist[start][finish]!=INF)〃判断起点终点之间是否连通{〃若连通，则给岀最短路径权值和具体路径方式cout«"最短路径为：,'«dist[start][finish]«endl;cout«"具体路径为:"«endl;temp=start;while(temp!=finish)cout«temp«,,->H;temp=p

6、ath[temp][finish];}cout«finishvvendl;}elsecoutvv”找不到对应路@"«endl;〃若不连通，返回找不到具体路径return0;}测试结果：选择一个有4个顶点（编号为0、1、2、3）和6条有向边的图，分别输入起点、终点和权值如下图所示。之后测试从0到2的最短路径。从数据可以看出，从0到2有三条路径：%10到1、1到2,权值为1+1=2；%10到2,权值为3；%10到3、3到2,权值为1+3=4。按照Floyd算法，应该选择权值为2的路径①作为最短路径。实验结果与预期相符BE:课件信网理论基础$验Floyd.exe-

7、□Xde汙初/只尸e

8、xa•n濡輸入迪笛个奴：6请输入各边起点、终点与权值：（顶点名称默认为0,1,……，3）0111121023031323131请输入要查询的起点和终点：02I最翹路径为>2具休路径为:0->1->2Processexitedafter64.37secondswithreturnvalue0请胺任意键继续・・・■//check函数用于判断连通性〃如果两点之间没有路径（最短路径为0）,则返回0〃否则返冋1〃构建矩阵并将元素全部初始化为INF〃对角线元素初始化为0实验四：图的连通性判断代码说明：判断图的连通性，只需要判断途中任意两个节点是否能通过

9、某种路径（依然采用有向的