云南大学软件学院计算机网络原理报告8.doc
.实验八、Link States Algorithm的实现序号： 姓名： _ 学号： _ 成绩 指导老师： 刘宇 刘春花 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。实验内容、拓扑结构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 structint 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; ABECD718122通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。A的转发表： B C D E 最短路径（A,E,D,C,B) (A,E,D,C) (A,E,D) (A,E) 成本值 6 5 3 14实验分析，回答下列问题（1）给出LSA算法的主要思想。答：首先引入一个辅助变量Di,它表示当前所找到的从始点到每个终点的最短路径的长度，它的初态为若有弧则为弧的权值，若无则为无穷大，且U为已经找到最短路径的结点的集合，首先比较不属于U集合的结点到始点的成本，将最小的结点并入U中，然后以该结点为桥梁找到始点到其余各终点的新的最短路径，即若始点到该点的成本与该点到终点的和小于始点到终点的成本，则设该成本为始点到终点的最短路径，然后再找出各终点到始点的最短路径集合的最小值的终点并入集合U，再循环执行上述步骤直到所有结点都并入U为止。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。A的转发表： B C D E 最短路径（A,E,D,C,B) (A,E,D,C) (A,E,D) (A,E) 成本值 6 5 3 1B的转发表： A C D E精品. 最短路径 （B,C,D,E,A) (B,C) (B,C,D) (B,C,D,E) 成本值 6 1 3 5C的转发表： A B D E 最短路径 （C,D,E,A) (C,B) (C,D) (C,D,E) 成本值 5 1 2 4D的转发表： A B C E 最短路径 （D,E,A) (D,C,B) (D,C) (D,E) 成本值 3 3 2 2E的转发表： A B C D 最短路径 （E,A) (E,D,C,B) (E,D,C) (E,D) 成本值 1 5 4 2如有侵权请联系告知删除，感谢你们的配合！精品
