云南大学软件学院计算机网络原理报(2).docx
云南大学软件学院计算机网络原理报实验八、Link States Algorithm的实现 序号： 姓名： _ 学号： _ 成绩 指导老师： 刘宇 刘春花 1实验目的： 通过编程模拟实现LSA. 2实验环境： VS.net软件开发平台，可以使用任何编程语言。 3实验要求 求网络中任何两个结点之间的最短路径。 得到任何一个节点上的转发表。 实验内容、拓扑结构 Initialization: 2 N' = u /*u is source node*/ 3 for all nodes j /* j is dest node*/ 4 if j adjacent 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 to j */ 15 until all nodes in N' 程序： #include<stdio.h> #include<stdlib.h> #define INFINITY 10000 /最大距离 #define MAX_NODES 50 /最大节点数 int distMAX_NODESMAX_NODES; /distij表示从 i 到 j 的距离 int pathMAX_NODES; typedef struct int vexnum; int vexMAX_NODES; graph; void init_graph(graph *g) int a,x,y=0; g->vexnum = 5; for(a =0;a<g->vexnum;a+) g->vexa=a; for(x=0;x<g->vexnum;x+) for(y=0;y<g->vexnum;y+) distxy=INFINITY; dist01 = 7;dist04 = 1; dist10 = 7;dist12 = 1; dist14 = 8;dist21 = 1; dist23 = 2;dist32 = 2; dist34 = 2;dist40 = 1; dist41 = 8;dist43 = 2; void shortest_path(int s, int t,int n) struct state int predecessor; /前驱节点 int length; /到起始点的距离 int label; stateMAX_NODES; int i,k,min; struct state * p; for(p=&state0; p<&staten; p+) p->predecessor = -1; p->length = INFINITY; p->label = 0; statet.length = 0; statet.label = 1; k = t; /k 是当前工作节点 do for(i=0; i<n; i+) if(distki!=0 && statei.label=0) if(statek.length+distki<statei.length) statei.length = statek.length+distki; statei.predecessor = k; k=0; min=INFINITY; for(i=0; i<n; i+) if(statei.label=0 && statei.length<min) k=i; min=statei.length; statek.label = 1; while(k!=s); i=0; k=s; do pathi = k; k = statek.predecessor; printf("<-%d",pathi); i+; while(k>=0); int main int m; graph g; g.vexnum = 5; init_graph(&g); printf("从A点出发到其他各点的最短路径如下所示：n"); printf("n注：0->A点;1->B点;2->C点;3->D点;4->E点n"); for(m=1;m<g.vexnum;m+) printf("n从编号为0的A点出发，到编号为%d的结点的最短路径为:n",m); shortest_path(g.vexm,g.vex0,g.vexnum); return 0; B 7 A 8 1 E 1 C 2 2 通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。 A的转发表： B C 最短路径 给出LSA算法的主要思想。 答：首先引入一个辅助变量Di,它表示当前所找到的从始点到每个终点的最短路径的长度，它的初态为若有弧则为弧的权值，若无则为无穷大，且U为已经找到最短路径的结点的集合，首先比较不属于U集合的结点到始点的成本，将最小的结点并入U中，然后以该结点为桥梁找到始点到其余各终点的新的最短路径，即若始点到该点的成本与该点到终点的和小于始点到终点的成本，则设该成本为始点到终点的最短路径，然后再找出各终点到始点的最短路径集合的最小值的终点并入集合U，再循环执行上述步骤直到所有结点都并入U为止。 通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。 A的转发表： B C D E 最短路径 （A,E,D,C,B) (A,E,D,C) (A,E,D) (A,E) 成本值 6 5 3 1 B的转发表： A C D E 最短路径 (B,C) (B,C,D) (B,C,D,E) 成本值 C的转发表： 最短路径 成本值 D的转发表： 最短路径 成本值 E的转发表： 最短路径 成本值 （B,C,D,E,A) 6 1 3 5 A （C,D,E,A) 5 B (C,B) 1 D (C,D) 2 E (C,D,E) 4 A （D,E,A) 3 B (D,C,B) 3 C (D,C) 2 E (D,E) 2 A （E,A) 1 B C (E,D,C,B) (E,D,C) 5 4 D (E,D) 2
