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

实验八、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 stdio.h #include string.h #include stdlib.h #include conio.h typedef int AdjMatrix[MAX][MAX]; typedef struct { int vexs[MAX]; 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++) { RW[i] = MG[v][i]; //初始化V对应的的其余点的权重 s[i] = 0; // 现在该点不属于节点子集 if (RW[i] == maxint) //初始化会回溯路径 { R[i] = 0; } else { R[i] = v; } } RW[v] = 0; s[v] = 1; //源节点作为最初的s子集 for (i = 1; i n; i++) { int temp = maxint; int u = v; //加入具有最小代价的邻居节点到s子集 for (j = 1; j = n; j++) { if ((!s[j]) (RW[j] temp)) { u = j; temp = RW[j]; } } s[u] = 1; //计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j = n; j++) { if ((!s[j]) (MG[u][j] maxint)) { int newRW = RW[u] + MG[u][j]; if (newRW RW[j]) { RW[j] = newRW; R[j] = u; //J点的回溯路径