云南大学软件学院计算机网络原理报告8计算机网络与通信_高等教育-大学课件.pdf

《云南大学软件学院计算机网络原理报告8计算机网络与通信_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《云南大学软件学院计算机网络原理报告8计算机网络与通信_高等教育-大学课件.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 else

2、D(j)=00 7 7 Loop 8 find i not in N such that D(i)is a minimum 9 add i to N 10 update D(j)for all j adjacent to i and not in N 11 D(j)=min(D(j),D(i)+c(i,j)12/*new cost to j is either old cost to j or known 13 shortest path cost to i plus cost from i to j*/14 until all nodes in N,程序：ncludestdio.h nclu

3、destdlib h define INFINITY 10000 ttdefine MAX_N0DES 50/最大距离/最大节点数 int distMAX_N0DESMAX_N0DES;/distij表示从 i 至 lj j 的距离 int pathMAX_N0DES;typedef struct int vexnum;int vexMAX_NODES;graph;void init_graph(graph*g)int a,x,y=0;g-vexnum=5;for(a=0:avexnum:a+)g-vexaZ=a;for(x=0;xvexnum;x+)for(y=0;yvexnum;y+)di

4、stxy 二 INFINITY;dist0 1 7;dist0 4 1；dist10 7;dist12 1;dist14 8;dist2l 1;dist23 2;dist32 2；dist34 2;dist 4 0 1；dist4 1 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+)

5、p-predecessor=T;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(statekJ length+distk：istatei length)statei length=statek length+distki;state Li 何编程语言实验要求求网络中任何两个结点之间的最短路径网络中至少有个节点得到任何一个节点上的转发表实验内容拓扑结构二程序最大距离最大节点数表示从至的距离二卄前驱节点到

6、起始点的距离是当前工作节点二二卄二二从态算法计算点到其它各点的最终输出的路山表的转发表最短路径成本值实验分析回答下列问题给出算法的主要思想答首先引入一个辅助变量它表示当前所找到的从始点到每个终点的最短路径的长度它的初态为若有弧则为弧的权值若然后以该结点为桥梁找到始点到其余各终点的新的最短路径即若始点到该点的成本与该点到终点的和小于始点到终点的成本则设该成本为始点到终点的最短路径然后再找出各终点到始点的最短路径集合的最小值的终点并入集合再循predecessor=k;k 二 0;min 二 INFINITY;for(i=0;in;i 卄)if(statei 1abel=0&statei 1eng

7、thmin)k=i;min=statei.length;statek label=1;while(k!=s);i 二 0；k 二 s;do pathi=k;k=statekpredecessor;printf(，?z:0);int main()int m;graph g；g vexnum=5;init_graph(&g);printf(“从 A 点出发到其他各点的最短路径如下所示：n);printf Cn 注：0-A 点；1-B 点；2-C 点；3-D 点；4-E 点n);for(m=l;mg vexnum;m+)printf Cn 从编号为 0 的 A 点出发，到编号为%d 的结点的最短路径

8、何编程语言实验要求求网络中任何两个结点之间的最短路径网络中至少有个节点得到任何一个节点上的转发表实验内容拓扑结构二程序最大距离最大节点数表示从至的距离二卄前驱节点到起始点的距离是当前工作节点二二卄二二从态算法计算点到其它各点的最终输出的路山表的转发表最短路径成本值实验分析回答下列问题给出算法的主要思想答首先引入一个辅助变量它表示当前所找到的从始点到每个终点的最短路径的长度它的初态为若有弧则为弧的权值若然后以该结点为桥梁找到始点到其余各终点的新的最短路径即若始点到该点的成本与该点到终点的和小于始点到终点的成本则设该成本为始点到终点的最短路径然后再找出各终点到始点的最短路径集合的最小值的终点并入集

9、合再循为:n,m);shortest_path(g vexm,g vexO,g.vexnum);return 0;通过链路状态算法计算 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 1 4.实验分析，回答下列问题（1）给出 LSA 算法的主要思想。答：首先引入一个辅助变量 Di,它表示当前所找到的从始点到每个终点的 最短路径的长度，它的初态为若有弧则为弧的权值，若无则为无穷大，且 U 为已 经找到最短路径的结点的集合，首先比较不属于 U 集合的结点到始点的成本，将

10、最小的结点并入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 1 B 的转发表:A C D E 最短路径 B C；(B,C,D)(B,C,D,E)何编程语言实验要求求网络中任何两个

11、结点之间的最短路径网络中至少有个节点得到任何一个节点上的转发表实验内容拓扑结构二程序最大距离最大节点数表示从至的距离二卄前驱节点到起始点的距离是当前工作节点二二卄二二从态算法计算点到其它各点的最终输出的路山表的转发表最短路径成本值实验分析回答下列问题给出算法的主要思想答首先引入一个辅助变量它表示当前所找到的从始点到每个终点的最短路径的长度它的初态为若有弧则为弧的权值若然后以该结点为桥梁找到始点到其余各终点的新的最短路径即若始点到该点的成本与该点到终点的和小于始点到终点的成本则设该成本为始点到终点的最短路径然后再找出各终点到始点的最短路径集合的最小值的终点并入集合再循(B,C,D,E,A)成本值

12、 6 1 3 5 C 的转发表:A B D E 最短路径(C,D,E,A)(C,B)(C,D)(C,D,E)成本值 5 1 2 4 D 的转发表:A B C E 最短路径(D,E,A)(D,C,B)(D,C)(D,E)成本值 3 3 2 2 E 的转发表:A B C D 最短路径(E,A)(E,D,C,B)(E,D,C)(E,D)成本值 1 5 4 2 何编程语言实验要求求网络中任何两个结点之间的最短路径网络中至少有个节点得到任何一个节点上的转发表实验内容拓扑结构二程序最大距离最大节点数表示从至的距离二卄前驱节点到起始点的距离是当前工作节点二二卄二二从态算法计算点到其它各点的最终输出的路山表的转发表最短路径成本值实验分析回答下列问题给出算法的主要思想答首先引入一个辅助变量它表示当前所找到的从始点到每个终点的最短路径的长度它的初态为若有弧则为弧的权值若然后以该结点为桥梁找到始点到其余各终点的新的最短路径即若始点到该点的成本与该点到终点的和小于始点到终点的成本则设该成本为始点到终点的最短路径然后再找出各终点到始点的最短路径集合的最小值的终点并入集合再循