《计算机网络原理实验八、Link-States-Algorithm的实现》由会员分享，可在线阅读，更多相关《计算机网络原理实验八、Link-States-Algorithm的实现（6页珍藏版）》请在装配图网上搜索。
1、 实验八、Link States Algorithm的实现序号： 姓名： 学号： 成绩 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4.实验内容、拓扑结构ABECD718122通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。算法提示：Initialization: 2 N = u /*u is source node*/3 for all nodes j /* j is dest node*/4 if j adjac
2、ent to u 5 then D(j) = c(u,j) 6 else D(j) = 7 8 Loop 9 find i not in N such that D(i) is a minimum 10 add i to N 11 update D(j) for all j adjacent to i and not in N : 12 D(j) = min( D(j), D(i) + c(i,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to i plus cost from i
3、 to j */ 15 until all nodes in N 4实验分析，回答下列问题（1）给出LSA算法的主要思想。 答： LSA算法的主要思想为：该算法用迭代算法，其性质是经算法的第次迭代后， 可知道个目的节点的最低费用路径。A：邻居节点发现与测试：各节点主动测试所有与之相邻的节点的状态。方法是 周期性的向邻,居节点广播简短的查询报文，通过接收邻居节点的响应报文,来获取与邻居的状态信息。 B：链路状态信息发布：根据收集到的状态信息，构造一个包含所有邻居列表在 内的分组LS，并通过洪泛法通告给算法作用区域内的所有节点。 C：路由选择算法：收到LS分组的节点，采用Dijkstra算法，为每
4、个节点选择 最短的路径。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。代码： #include#include#define MAXV 20#define MAXSIZE 20#define MAXLEN 500#define INF 10000/*用表示*/int a=0;typedef structint num; char nameMAXSIZE; char contentMAXLEN;VertexType;typedef struct int edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV;MGrap
5、h;int visitedMAXV;int pMAXV;void Path(MGraph g,int i,int j,int k)/*确定路径上第k+1个节点的编号*/int s; if(pk=j)/*找到一条路径*/ a+;/*路径的条数值加*/ printf(第%d条:n,a); for(s=0;s,g.vexsps.name); printf(n); s=0; while(sg.vexnum) if(s!=i)/*保证找到的是简单路径*/ if(g.edgespks!=INF&visiteds=0) /*当vk与vs之间有边存在且vs未被访问过*/ visiteds=1;/*置访问标志位
6、为,即已访问的*/ pk+1=s;/*将顶点s加入到p数组中*/ Path(g,i,j,k+1); visiteds=0;/*重置访问标志位为，以便该顶点能被重新使用*/ s+; void Display(MGraph g,int i,int j)int k; p0=i; for(k=0;k,g.vexsk.name);/*依次输出路径中的节点*/void Dispath(MGraph g,int dist,int path1,int s,int n,int v0,int i) if(si=1&i!=v0)/*当v0不等于i，且is*/ printf(n从%s到%s的最短路径是:n,g.vex
7、sv0.name,g.vexsi.name); printf(%s-,g.vexsv0.name); Path2(g,path1,i,v0);/*调用ppath函数，输出路径中的节点*/ printf(%s ,g.vexsi.name); printf(路径长度：%dn,disti); void Dijkstra(MGraph g,int v0,int p) int distMAXV,path1MAXV; int sMAXV; int mindis,i,j,u,n=g.vexnum; for(i=0;in;i+) disti=g.edgesv0i;/*距离初始化*/ si=0;/*s置空*/
8、if(g.edgesv0iINF)/*路径初始化*/ path1i=v0; else path1i=-1; sv0=1;path1v0=0;/*源点编号v0放入s中*/ for(i=0;in;i+) mindis=INF; u=-1; for(j=0;jn;j+)/*选取不在s中具有最小距离的节点u*/ if(sj=0&distjmindis) u=j; mindis=distj; su=1;/*顶点u加入s中*/ for(j=0;jn;j+)/*修改不在s中的节点的距离*/ if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) /*修正disti,pa
9、th1i*/ distj=distu+g.edgesuj; path1j=u; Dispath(g,dist,path1,s,n,v0,p);/*输出最短路径*/void Search(MGraph g)printf(节点：n1.An2.Bn3.Cn4.Dn5.E); int i=0,j=0; char s=0; printf(nn请选择出发节点的编号：); scanf(%d,&i); printf(请选择目的节点的编号：); scanf(%d,&j); for(int k=0;kg.vexnum;k+)/*g.vexnum表示网中的顶点个数*/ if(i=g.vexsk.num) i=k;/
10、*在网中找到其编号与输入的出发景点的编号相同的顶点*/ for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/*在网中找到其编号与输入的目地景点的编号相同的顶点*/ Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/void main()int i=0,j=0;int b5=1,2,3,4,5;/*整型数组,用来给每个顶点的编号进行赋值*/char *c5=A,B,C,D,E;/*字符串指针数组,用来给每个顶点的名称进行赋值*/ MGraph g;/*定义一个MGraph类型的变量g,用来创建一个无向网*/
11、 /*建立一个无向网，并用无向网表示节点的平面图*/ int A55= /*用INF表示对应顶点间没有直达的路径，用其它整型变量表示对应顶点间有直达的路径，且路径的长度就是该整型变量的值*/ 0,7,INF,INF,1, 7,0,1,INF,8, INF,1,0,2,INF, INF,INF,2,0,2, 1,8,INF,2,0 ; g.vexnum=5;/*网中顶点的个数为*/ g.arcnum=6;/*网中边的个数为*/ for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.edgesij=Aij;/*建立无向网的邻接矩阵*/ for(i=0;ig.v
12、exnum;i+) g.vexsi.num=bi;/*给每个节点一个编号*/ strcpy(g.vexsi.name,ci);/*通过字符串复制函数给每个节点一个名称*/ int select;/*定义一个整型变量,用来输入不同的选择*/ do/*可提供循环输入选择,当输入的选择为时,退出循环*/ printf(n1.求节点间的最短路径0.退出); printf(n请选择操作:); scanf(%d,&select); switch(select) /*判断select的值，根据其值跳转到相应的子模块继续执行*/ case 1: Search(g);/*节点间的最短路径*/ break; case 0:/*退出程序*/ break; while(select!=0);/*当select的值不为时，继续循环*/截图：
计算机网络原理实验八、Link-States-Algorithm的实现
