链路状态路由算法实验.docx
《链路状态路由算法实验.docx》由会员分享，可在线阅读，更多相关《链路状态路由算法实验.docx（13页珍藏版）》请在冰点文库上搜索。
链路状态路由算法实验
实验二链路状态路由算法的实验
一、实验目的：
了解链路状态路由算法的原理以及具体过程。
二、实验原理：
链路状态算法实现的基本步骤：
1、发现他的邻接点，并知道其网络的地址。
2、测量到各邻接点的延迟或开销。
3、构造一个分组，分组中包含所有他刚刚收到的信息。
4、将这个分组发送给其他的路由器。
5、计算出到每一个其他路由器的最短路径
三、链路状态路由的核心算法（迪加克拉算法）：
voiddijkstra（ints,intt,intpath[]）{
structstate{//存放节点数据
intpredecessor;//父节点
intlength;//权值
boollable;//访问状态
}state[MAX_NODES];
inti,j,k,min;
structstate*p;
for（p=&state[0];p<&state[Vnums];p++）//初始化节点数据
{
p->predecessor=-1;
p->length=INFINITY;
p->lable=false;
}
state[t].length=0;
state[t].lable=true;
k=t;
do{
for（inti=0;iif（（dist[k][i]!
=0）&&（state[i].lable==false））
if（state[k].length+dist[k][i]{
state[i].predecessor=k;//记录节点
cout<";
state[i].length=state[k].length+dist[k][i];//路径长度
}
k=0;
min=INFINITY;
for（inti=0;iif（（state[i].lable==false）&&（state[i].length{
min=state[i].length;
k=i;
}
state[k].lable=true;
}while（k!
=s）;
cout<}
四、流程图：
核心算法（迪加克拉算法）流程图：
五、程序截图：
1、
路由表信息：
2、不同两点间的最短路径：
六、源代码
#include
#include
#definerouteTable"routeTable.txt"
usingnamespacestd;
constintMAX_NODES=1024;
constintINFINITY=100000;
intdist[MAX_NODES][MAX_NODES];//用于存放网络拓扑结构连接矩阵
intstaticVnums;//总的节点数
voidinitDist（）{//初始化邻接矩阵
for（inti=0;ifor（intj=0;jdist[i][j]=0;
}
voidcreatRouteMap（intVnums）{//创建网络拓扑结构的邻接矩阵
for（inti=0;i{
cout<<"输入第"<for（intj=0;j{
cout<"<cin>>dist[i][j];
}
}
}
voidsaveRoute（ofstream&routeTables）{//保存路由信息
routeTables<<"路由邻接矩阵为：
";
routeTables<<"\n";
routeTables<<"**********************************";
routeTables<<"\n";
for（inti=0;i{
for（intj=0;j{
routeTables<}
routeTables<<"\n";
}
}
voiddijkstra（ints,intt,intpath[]）{
structstate{//存放节点数据
intpredecessor;//父节点
intlength;//权值
boollable;//访问状态
}state[MAX_NODES];
inti,j,k,min,print;
structstate*p;
for（p=&state[0];p<&state[Vnums];p++）//初始化节点数据
{
p->predecessor=-1;
p->length=INFINITY;
p->lable=false;
}
state[t].length=0;
state[t].lable=true;
k=t;
cout<<"最短路径为：
"<do{
for（inti=0;iif（（dist[k][i]!
=0）&&（state[i].lable==false））
if（state[k].length+dist[k][i]{
state[i].predecessor=k;//记录节点
cout<";
state[i].length=state[k].length+dist[k][i];//路径长度总和
}
k=0;
min=INFINITY;
for（inti=0;iif（（state[i].lable==false）&&（state[i].length{
min=state[i].length;
k=i;
}
state[k].lable=true;
}while（k!
=s）;
cout<}
voidaddRoute（）{//添加一个路由及结点信息
charch;
do{
cout<<"添加一个路由:
"<Vnums=Vnums+1;
cout<<"输入第"<for（intj=0;j{
cout<"<cin>>dist[Vnums-1][j];//对应行的信息
dist[j][Vnums-1]=dist[Vnums-1][j];//对应列的信息
}
cout<<"继续添加（y或者n）：
"<cin>>ch;
if（ch=='n'）break;
}while（ch=='y'）;
}
voiddeleteRoute（）{
charch;
intdelNum;
do{
cout<<"输入删除路由结点号:
"<cin>>delNum;
for（intj=0;j{
dist[delNum-1][j]=0;//对应行的信息
dist[j][delNum-1]=dist[delNum-1][j];//对应列的信息
}
cout<<"继续删除（y或者n）：
"<cin>>ch;
if（ch=='n'）break;
}while（ch=='y'）;
}
voidchangeRoute（）{
inti,j;
cout<<"输入要修改的结点1：
"<cin>>i;
cout<<"输入要修改的结点2：
"<cin>>j;
cout<<"输入修改的权值：
"<cin>>dist[i-1][j-1];
}
voiddisplayRouteInfo（）{
cout<<"**********************************"<cout<<"路由表信息:
"<for（inti=0;i{
for（intj=0;j{
cout<}
cout<<"\n";
}
}
intmain（）{
intdesNode,rouNode;
intpath[MAX_NODES];
intchange;
charch;
ofstreamrouteTables;
//初始化权值矩阵
initDist（）;
cout<<"输入路由总节点数：
"<cin>>Vnums;
do{
//主菜单界面
cout<<"\t"<<"============================="<cout<<"\t"<<"1.创建路由表"<cout<<"\t"<<"2.增加路由"<cout<<"\t"<<"3.删除路由"<cout<<"\t"<<"4.修改路由"<cout<<"\t"<<"5.找两个路由间的最短路径"<cout<<"\t"<<"6.保存路由表到文件"<cout<<"\t"<<"7.显示路由表信息"<cout<<"\t"<<"8.退出"<cout<<"\t"<<"============================="<//cout<<"输入路由总节点数：
"<//cin>>Vnums;
cout<<"选择操作（1-8）：
"<cin>>change;
switch（change）
{
case1:
creatRouteMap（Vnums）;system（"pause"）;system（"cls"）;break;case2:
addRoute（）;system（"pause"）;system（"cls"）;break;
case3:
deleteRoute（）;system（"pause"）;system（"cls"）;break;
case4:
changeRoute（）;system（"pause"）;system（"cls"）;break;
case5:
cout<<"输入目标节点和源节点：
"<cin>>desNode;
cin>>rouNode;
dijkstra（desNode,rouNode,path）;//求最短路径
system（"pause"）;
system（"cls"）;
break;
case6:
routeTables.open（routeTable）;
if（routeTables==NULL）
{
cout<<"打开文件夹错误:
"<getchar（）;
exit（0）;
}
//保存文件
saveRoute（routeTables）;
routeTables.close（）;
system（"cls"）;
break;
case7:
displayRouteInfo（）;system（"pause"）;system（"cls"）;break;
case8:
return0;
default:
system（"cls"）;break;
}
cout<<"返回选择菜单（y或者n）：
"<cin>>ch;
if（ch=='n'）break;
}while（ch=='y'）;
system（"pause"）;
return0;
}
七、心得体会：
通过做练习编写链路状态路由算法的实验，我更进一步加深了对链路状态路由原理的理解，对网络过程中网络节点的信息传输与通信有了更进一步认识。
同时，对迪加克拉求最短路径算法的设计与原理加深了理解。
升级会员 