实验八、Link States Algorithm的实现.doc

实验八、Link States Algorithm的实现序号： 姓名： 学号： 成绩 指导教师 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4实验分析，回答下列问题（1）给出LSA算法的主要思想。 邻居节点发现与测试：各节点主动测试所有与之相邻的节点的状态。方法是 周期性的向邻 居节点广播简短的查询报文，通过接收邻居节点的响应报文 来获取与邻居的状态信息。 链路状态信息发布：根据收集到的状态信息，构造一个包含所有邻居列表在 内的分组LS，并通过洪泛法通告给算法作用区域内的所有节点。 路由选择算法：收到LS分组的节点，采用Dijkstra算法，为每个节点选择 最短的路径。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。代码:#include#include void D(int ,int ,int *,int *,int * );/dijkstra算法void p(int ,int ,int ,int *,int *);/输出结果void main() int i,j,t; int n,v,u; int *MGraph; /矩阵 int *RoutWeight; /最短路径代价 int *Rout; /回溯节点 while(1) printf(结点的个数为: ); scanf(%d,&n); printf(输入邻接矩阵:n); MGraph=(int *)malloc(sizeof(int)*(n+1); /构建动态存储矩阵 for (i = 1; i = n; i+) MGraphi=(int *)malloc(sizeof(int)*(n+1); for (j = 1; j = n; j+) /输入代价矩阵 for (t = 1; t = n; t+) scanf(%d,&MGraphjt); RoutWeight = (int *)malloc(sizeof(int)*n); Rout = (int *)malloc(sizeof(int)*n); printf(你输入的源节点：); scanf(%d,&v); D(n, v, RoutWeight, Rout, MGraph); /调用dijkstra算法for(i = 1; i = n ; i+) if(i!=v) printf(从%d 到%d 的路径距离是%dn,v,i,RoutWeighti); p(n,v,i, RoutWeight, Rout); void D(int n,int v,int *RoutWeight,int *Rout,int *MGraph) int i; int j; int maxint =0;/定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ; /定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) * n); /初始化最小路径代价和前一跳节点值 for (i = 1; i = n; i+) RoutWeighti = MGraphvi; /初始化V对应的的其余点的权重 si = 0; / 现在该点不属于节点子集 if (RoutWeighti = maxint) /初始化会回溯路径 Routi = 0; else Routi = v; RoutWeightv = 0; sv = 1; for (i = 1; i n; i+) int temp = maxint; int u = v; /加入具有最小代价的邻居节点到s子集 for (j = 1; j = n; j+) if (!sj) & (RoutWeightj temp) u = j; temp = RoutWeightj; su = 1; /计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j = n; j+) if (!sj) & (MGraphuj maxint) int newRoutWeight = RoutWeightu + MGraphuj; if (newRoutWeight = 1; j