计算机网络原理实验八实验报告.doc

实验八、Link States Algorithm的实现序号： 姓名： 学号： 成绩 指导老师： 刘春花，刘宇 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4实验分析，回答下列问题（1）给出LSA算法的主要思想。（1）邻居节点发现与测试：各节点主动测试所有与之相邻的节点的状态。方法是 周期性的向邻 居节点广播简短的查询报文，通过接收邻居节点的响应报文 来获取与邻居的状态信息。 （2）链路状态信息发布：根据收集到的状态信息，构造一个包含所有邻居列表在 内的分组LS，并通过洪泛法通告给算法作用区域内的所有节点。 （3）路由选择算法：收到LS分组的节点，采用Dijkstra算法，为每个节点选择 最短的路径。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。代码#define MAX 20 /图中顶点数的最大值#define MAXedg 30 /图中边数的最大值#include #include #include #include typedef int AdjMatrixMAXMAX;typedef structint vexsMAX; AdjMatrix arcs;MG;/图的矩阵表示法。 void Dijkstra(int n,int v,int *RW,int *R,int *MG) int i; int j; int maxint =00000;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ; /定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) * n); /初始化最小路径代价和前一跳节点值 for (i = 1; i = n; i+) RWi = MGvi; /初始化V对应的的其余点的权重 si = 0; / 现在该点不属于节点子集 if (RWi = maxint) /初始化会回溯路径 Ri = 0; else Ri = v; RWv = 0; sv = 1; /源节点作为最初的s子集 for (i = 1; i n; i+) int temp = maxint; int u = v; /加入具有最小代价的邻居节点到s子集 for (j = 1; j = n; j+) if (!sj) & (RWj temp) u = j; temp = RWj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j = n; j+) if (!sj) & (MGuj maxint) int newRW = RWu + MGuj; if (newRW = 1; j-) printf(%d - ,wayj); printf(%dn,u);void Dijkstra(int ,int ,int *,int *,int * );void ShowPath(int ,int ,int ,int *,int *);void main()/主函数char choice = x;while(1) system(cls);printf(ntt*nn);printf(ttt1. 查找两节点间最短路径:nn);printf(ttt2. 退出nn);printf(ntt*nn);printf(Please enter your choice(1/2):n );choice = getchar();switch(choice)case 1: int i,j,t; int n,v,u; int *MG; /矩阵 int *RW; /最短路径代价 int *R; /回溯节点 printf(请输入结点个数: ); scanf(%d,&n); printf(结点之间的链接代价为:n); MG=(int *)malloc(sizeof(int)*(n+1);/构建动态存储矩阵 for (i = 1; i = n; i+) MGi=(int *)malloc(sizeof(int)*(n+1); for (j = 1; j = n; j+) /输入代价矩阵 for (t = 1; t = n; t+) scanf(%d,&MGjt); RW = (int *)malloc(sizeof(int)*n);R= (int *)malloc(sizeof(int)*n);printf(2请输入起始节点：n);scanf(%d,&v);getchar();printf(2请输入目标结点：n);scanf(%d,&u);getchar(); Dijkstra(n, v, RW, R, MG); /调用dijkstra算法 for(i = 1; i = n ; i+) if(i!=v) printf(从%d 到%d 的路径距离是%dn,v,i,RWi); /printf(结点%d 的前一个结点是%d n,i,Routi); ShowPath(n,v,i, RW, R); doprintf(是否继续? Y/N);char ch;int flag=1;scanf(%c,&ch);getchar();if(ch = Y | ch = y) /继续flag = 1;i = 1;printf(2请输入起始节点：n);scanf(%d,&i);getchar();printf(2请输入目标结点：n);scanf(%d,&j);getchar();getchar();continue ;elseflag = 0; /不