云南大学软件学院计算机网络原理报告8

1、实验八、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 els

2、e 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 程序

3、：#include#include#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;avexnum;a+)g-vexa=a;for(x=0;xvexnum;x+)for(y=0;yvexn

4、um;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 sta

5、te * p; for(p=&state0; ppredecessor = -1; p-length = INFINITY; p-label = 0; statet.length = 0; statet.label = 1; k = t; /k 是当前工作节点 do for(i=0; in; i+) if(distki!=0 & statei.label=0) if(statek.length+distkistatei.length) statei.length = statek.length+distki; statei.predecessor = k; k=0; min=INFINITY;

6、 for(i=0; in; i+) if(statei.label=0 & statei.lengthmin) k=i; min=statei.length; statek.label = 1; while(k!=s); i=0; k=s; do pathi = k; k = statek.predecessor; printf(=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;mg

7、.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,它表示当前所找到的从始点到每个终点的最短路径的长度，它的初态为若有弧则为弧的权值，若无则为无穷大

8、，且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)