云南大学软件学院计网实验8

1、课程:姓名:通过链路状态算法计算云南大学软件学院实验报告计算机网络原理实验任课教师：_学号：专业：成绩:实验八、Link States Algorithm 的实现1. 实验目的：通过编程模拟实现 LSA.2. 实验环境：VS.net软件开发平台，可以使用任何编程语言。3. 实验要求4个节点)。(1) 求网络中任何两个结点之间的最短路径(网络中至少有(2) 得到任何一个节点上的转发表。4. 实验内容、拓扑结构A点到其它各点的cost，最终输出A的路由表。# include<stdio.h># include<stdlib.h># definemaxlen 10# defi

2、nelarge 999typedefstructintvexnum;(该处设置路径最大值，表示不存在该路线)char vexsmaxlen;int arcsmaxlenmaxlen; graph;void init_graph(graph *g)int i = 0,j = 0;g -> vexnum = 5;for (i = 0; i < 5; i+)for (j = 0; j < 5; j+) g -> arcsij = 999;初始化图/根据题目此处将图的节点数初始化为 经过两层循环将条路径初始化为无穷大g -> arcs04 = 1; g -> arc

3、s12 = 1; g -> arcs40 = 1; g -> arcs21 = 1;g -> arcs23 = 2;g -> arcs14 = 8;g -> arcs34 = 2;g -> vexs0 ='A'g -> vexs1 ='B'g -> vexs2 ='C'g -> vexs3 ='D'g -> vexs4 ='E'g -> arcs32 = 2; g -> arcs41 = 8; g -> arcs43 = 2;/ 将节点值

4、初始化void shortpath_dijkstra(graph g)/ 寻找最短路径intcostmaxlenmaxlen;/costij:节点 i 到节点 j 的成本intdistmaxlen;/disti:源节点到 i 节点的距离或者是成本intpathmaxlen;/ 已经经过了的节点intsmaxlen;/ 如果 si= 1, 那么 i 节点已经纳入最短路径集合inti,j,v0,min,u;char e;printf("Input the source point(AorBorCorDorE):");/ 用户输入源节点scanf( "%c",

5、&e);switch (e)case 'A'v0=0;break ;case 'B'v0=1; break ; case 'C' v0=2; break ; case 'D' v0=3; break ; case 'E' v0=4;break ;for (i = 0; i < g.vexnum; i+)for (j = 0; j < g.vexnum; j+)costij = g.arcsij;for (i = 0; i < g.vexnum; i+)disti = costv0i;/ 初

6、始化源节点到各个节点的成本，如果与源节点相邻则成本为权值，否则为无穷大if (disti < large && disti > 0)pathi = v0;si = 0;sv0 = 1;for (i = 0; i < g.vexnum; i+)min = large;u = v0;for (j = 0; j < g.vexnum; j+)if (sj = 0 && distj < min)min = distj;u = j;su = 1;for (j = 0; j < g.vexnum; j+)if (sj = 0 &&

7、amp; distu + costuj < distj)distj = distu + costuj;pathj = u;printf( "Output%cnn" ,e);for (i = 0; i < g.vexnum; i+)if (si = 1)u = i;while (u != v0)printf(" %c <- " ,g.vexsu);u = pathu;printf(" %c " ,g.vexsu);printf(" :%d n" ,disti);else printf( "

8、 %c <- %c: no path n" ,g.vexsi,g.vexsv0);int main()graph g; init_graph（&g）;shortpath_dijkstra（g）;system（ "pause"）;return 0;从A点开始，寻找到其余各点的最短路径截图如下:4.实验分析，回答下列问题（1）给出LSA算法的主要思想。1 、路由器初始化 （所有节点的） 状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。2、 路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。3、 路由器在所有的暂时性节点中选择距离V1

9、的权值最低的节点。这个节点将是 新的T节点。4、 如果这个节点不是V2 （目的节点），路由器则返回到步骤5。5、如果节点是 V2,路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。（2 ）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。AB: A->E->D->C->B 最小成本为：6AC: A->E->D->C最小成本为：5AD: A->E->D最小成本为：3AE: A->E最小成本为：1BD:B->C->D最小成本为：3BC:B->C最小成本为1BE:B->C->D->E最小成本为：5CD:C->D最小成本为：2CE:C->D->E最小成本为：4DE:D->E最小成本为：2（如果是源节点与目的节点反过来则路反过来即可） 各个节点的转