中南大学计算机网络实验报告Word文件下载.docx
《中南大学计算机网络实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《中南大学计算机网络实验报告Word文件下载.docx（19页珍藏版）》请在冰点文库上搜索。
布置好各个模拟路由，以及路由的路程权值如何获取。
接着就是核心算法的实现，如何计算任意两个路由之间的最短路径问题。
用到的是dijkstra算法。
Dijkstra算法按照从给定起点到图中顶点的距离，顺序求出最短的路径，首先，它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，一次类推，推而广之，再第i次迭代开始之前，算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。
这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一颗子树Ti，因为所有边的权值都是非负数，可以从与Ti的顶点相邻的顶点中找到下一个和起点最接近的顶点。
和Ti的顶点相邻的顶点的集合称为“边缘顶点”，以他们为候选对象，Dijkstra算法可以从中选出一个最接近起点的顶点。
为了确定第I个最接近的顶点，对于每一个边缘顶点u，该算法求出它到最近的树中顶点v的距离以及从起点到v得最短路径长度dv的和，再从中选出具有最小和的顶点。
此次实验主要是运用路由算法来处理路由当中的一些问题，利用Dijkstra算法处理最短路径的问题，在实验中这点已经得到了充分地体现。
下面是该算法的流程图：
核心算法代码如下。
其中每个顶点用一个类来封装含有两个属性，一个是路由编号，一个是到某个路由的最短路径初始值为无限大。
voidDijkstra（int*arcs[],int*R[],intRL[],intvexnum）{
//迪杰斯特拉算法
intv0;
//定义源节点
bool*visit=newbool[vexnum];
//已经确定最短路径的节点的集合
cout<
<
"
请输入起始节点:
;
cin>
>
v0;
endl;
for（intcnt=0;
cnt<
vexnum;
cnt++）{//进行主要的循环之前的初始化
visit[cnt]=FALSE;
RL[cnt]=arcs[v0][cnt];
if（RL[cnt]<
INFINITY）{
R[cnt][0]=v0;
R[cnt][1]=cnt;
}
}//for
RL[v0]=0;
//源节点的标志
visit[v0]=TRUE;
//初始化已经找到最短路径的点集合
for（inti=1;
i<
i++）{//dijkstra算法的主要循环
intmin=INFINITY;
intv=v0;
for（intj=0;
j<
j++）
if（!
visit[j]）
if（RL[j]<
min）{
v=j;
min=RL[j];
}
visit[v]=TRUE;
//离v0顶点最近的v加入到s集
for（intk=0;
k<
k++）//更新当前最短路径及距离
if（!
visit[k]&
&
（min+arcs[v][k]<
RL[k]））{
//modifyshortestr[j]andRL[j]
RL[k]=min+arcs[v][k];
updateRouteLen（R[k],R[v],k,vexnum）;
}//if
}//for
delete[]visit;
visit=NULL;
}//Dijkstra
完成核心算法后，对于每个路由器运行一次Dijkstra算法就可以计算出该路由到其他各个路由的最短路径。
四、实验过程及结果
本实验用6个节点进行模拟，首先输入节点个数，再依次输入节点的标识符和到邻居节点的标识符和距离。
以end为结束符。
运行结果如下：
请输入路由节点总个数：
6
请输入路由节点标识符：
a
请输入节点：
a的邻居节点的标识符及其到邻居节点的距离：
b
8
f
3
end
b的邻居节点的标识符及其到邻居节点的距离：
c
5
d
2
e
4
c的邻居节点的标识符及其到邻居节点的距离：
10
d的邻居节点的标识符及其到邻居节点的距离：
e的邻居节点的标识符及其到邻居节点的距离：
f的邻居节点的标识符及其到邻居节点的距离：
End
路由表结果
五、实验心得
本次实验，主要的就是一个著名算法的运用，当然通过本次实验我对链路路由算法也有了进一步的认识与了解。
从这次的实验中我不但学会了一个新的算法，进一步锻炼了我的编程能力而且我也对路由相关内容有了更深刻的了解。
六、附录：
源代码
packagedstverctor;
/**
*描述两个路由节点之间关系的类
*
*/
publicclassDistanceNode{
//publicRouteNodesrc;
//源节点
//publicDistanceNode（RouteNodesrc）{
//this.src=src;
//}
publicStringdst;
//目标节点
publicintdistance;
//两者之间的距离
publicStringpath;
//经过的第一个路径节点，即线路
publicDistanceNodenext;
//下一个节点
publicDistanceNode（）{
}
publicDistanceNode（Stringdst,intdistance,Stringpath）{
this.dst=dst;
this.distance=distance;
this.path=path;
/**
*根据节点标识符，得到路由节点到指定节点的距离
*@paramkey指定节点标识符
*@return如果找到，则返回这个关系类节点，否则返回null。
*int
publicDistanceNodefindNode（Stringkey）{
DistanceNodedn=this;
while（dn!
=null）{
if（dn.dst.equals（key））{
returndn;
}
dn=dn.next;
returnnull;
*根据key向链表中修改或增加一个节点，如果存在dst.equal（key）的点并且他的distance大于要插入的distance，则更改其distance，否则向链表末尾插入新节点
*@paramkey
*@paramdistance
*@parampath
*void
publicvoidaddNode（Stringkey,intdistance,Stringpath）{
DistanceNodedn=findNode（key）;
if（null!
=dn）{//如果找到了节点
if（dn.distance>
distance）
dn.distance=distance;
}else{
DistanceNodedn1=this;
while（dn1.next!
dn1=dn1.next;
DistanceNodenode=newDistanceNode（）;
node.distance=distance;
node.dst=key;
node.path=path;
dn1.next=node;
node.next=null;
publicvoidprint（）{
System.out.println（"
目地节点：
+dn.dst+"
距离：
+dn.distance+"
线路：
+dn.path）;
while（dn.next!
System.out.println（"
}
*路由的唯一标识符类
publicclassRouteKey{
Stringkey;
//路由节点的唯一标识符
RouteKeynext;
//路由表中的下一个路由节点
publicRouteKey（）{
publicRouteKey（Stringkey）{
this.key=key;
RouteKeyrk=this;
System.out.print（rk.key+"
||"
）;
while（rk.next!
rk=rk.next;
System.out.print（rk.key+"
*路由节点
publicclassRouteNode{
DistanceNodeold;
//老路由表
DistanceNodecurrent;
//新路由表
RouteKeyneighbour;
//存储邻居节点的链表头结点
//跟新路由表
publicvoidupdateCurrent（）{
saveCurrent（）;
//路由表变化前保存当前的路由表
RouteNodenb;
//邻居节点
RouteKeyrk=neighbour;
while（null!
=rk）{
//System.out.println（"
------------"
+rk.key+"
-------"
nb=DistVerctor.map.get（rk.key）;
//由节点标记符得到路由节点
//System.out.println（"
+nb.key+"
DistanceNodedn=nb.old;
//得到邻居节点的老路由表
//排除自己在内，避免重新计算自己到邻居节点
if（dn.dst.equals（key））{
System.out.println（"
dn=dn.next;
intdistTonb=0;
if（dn!
=null）
distTonb=current.findNode（nb.key）.distance;
//到邻居节点的距离
while（null!
=dn）{
//排除自己在内，避免重新计算自己到邻居节点
if（dn.dst.equals（key））{
System.out.println（"
dn=dn.next;
}else{
//修改新路由表，
//如果当前节点到dn的距离小于当前节点到邻居节点nb+nb到dn的距离，则修改路由表
//如果不存在当前节点到dn的路径，则在路由表最后新添加该路径
current.addNode（dn.dst,dn.distance+distTonb,nb.key）;
//指向下一个邻居节点
*将当前表保存为旧表
*
publicvoidsaveCurrent（）{
DistanceNodecnode=current;
DistanceNodeonode=newDistanceNode（）;
copy（cnode,onode）;
//得到cnode的备份
old=onode;
while（cnode.next!
onode.next=newDistanceNode（）;
copy（cnode.next,onode.next）;
cnode=cnode.next;
onode=onode.next;
publicvoidcopy（DistanceNodesrc,DistanceNodedst）{
dst.distance=src.distance;
dst.dst=src.dst;
dst.path=src.path;
System.out.println（key+"
的邻居节点：
neighbour.print（）;
老路由表：
old.print（）;
新路由表：
current.print（）;
升级会员 